LeetCode_ 77_ combination

Topic link

• https://leetcode.cn/problems/combinations/

Title Description

Given two integers n and k, Return range [1, n] All the possibilities in k Combination of numbers .

You can press In any order Return to the answer .

Example 1：

 Input ：n = 4, k = 2
 Output ：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2：

 Input ：n = 1, k = 1
 Output ：[[1]]

Tips ：

• 1 <= n <= 20
• 1 <= k <= n

Their thinking

backtracking

The combination problem is abstracted into the following tree structure , Each time you select an element from the collection , The selectable range shrinks with the selection , Adjust the selectable range . It can be found in the figure n It's the width of a tree ,k It's the depth of a tree . Every time a leaf node is searched in the figure , We found a result

Retrospective trilogy

• Parameters and return values of recursive functions
  • n,k,startIndex, Used to record recursion in this layer , Where the collection starts traversing
  • path: Used to store qualified results
  • ans: Set used to store qualified results
• Termination condition of backtracking function
  • To the leaf node . That is to say path The size of this array is k, It indicates that a subset size of k A combination of , In the picture path What you save is the path from the root node to the leaf node .
  • Use at this time ans Array saves the results , And terminate the recursion of this layer
• Single layer logic
  • use for Loop traversal , Specifically, every time from startIndex To traverse the , And then use path Save the retrieved node i

Pruning optimization

As shown in the figure , Where you can prune is at every level of recursion for Start position of cycle selection

• If for The number of elements after the starting position of the loop selection is not enough for us , Then there is no need to search

AC Code

class Solution {
    
public static List<List<Integer>> combine(int n, int k) {
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backTracing(n, k, 1, path, ans);
        return ans;
    }

    private static void backTracing(int n, int k, int startIndex, List<Integer> path, List<List<Integer>> ans) {
    

        // Termination conditions 
        if (path.size() == k) {
    
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
    
            path.add(i);
            backTracing(n, k, i + 1, path, ans);
            // to flash back 
            path.remove(path.size() - 1);
        }
    }
}