“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The combination of buckle 77 is as follows:

Given two integers n and k, return all possible combinations of k numbers in the range [1, n].

You can return the answers in any order.

Example 1:

Input: n = 4, k = 2 output: [[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4],]Copy the code

Example 2:

Input: n = 1, k = 1 Output: [[1]]Copy the code

A, thinking

This one is generating all possible combinations, and that’s done recursively, of course.

The general steps are as follows:

  1. Because the interval is[1, n], so from1start
  2. If the size of the current layer result iskThe current result is added to the result set

For example

Here, n = 4 and k = 2 are used as examples

  1. To choose the1The results you can get are[1, 2].[1, 3] 和 [1, 4]
  2. Then choose2The results you can get are[2, 3].[2, 4]
  3. Then choose3You can get[3, 4]
  4. Return the resulting result set

There are two noteworthy points:

  1. At the end of each iteration of the current layer, the element added to the current layer should be removed
  2. Pruning should be appropriate: when the length of a temporary set of results and the number of remaining elements do not add upkIf large, the recursion of the current level should be terminated. (E.gn = 4, k = 3In the recursive process, the first element of a group is selected3, you should stop recursing downward immediately. Because there is only one element left, even if both were selected, the result would not be correct.

Second, the implementation

The implementation code

List

is used to store a set of results

    List<Integer> temp = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }

    public void dfs(int cur, int n, int k) {
        / / the pruning
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // Record the result
        if (temp.size() == k) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        temp.add(cur);
        dfs(cur + 1, n, k);
        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k);
    }
Copy the code

The test code

    public static void main(String[] args) {
        new Number77().combine(4, 3);
    }
Copy the code

The results of

Third, summary

I see the force buckle above can also use lexicographical order method to solve this problem, this method is more difficult to understand, interested can go to force buckle official problem solution look!

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section