Leetcode 77 combination -- backtracking method

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/combinations

---

The question ：

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

---

Reference article

Ideas ：

This topic is the topic of backtracking algorithm , About backtracking algorithms , You can read this article of code Capriccio 《 Theoretical basis of backtracking algorithm ！》 Make a preliminary understanding .

Backtracking algorithm template framework ：

void backtracking( Parameters ) {
    
    if ( Termination conditions ) {
    
         Store results ;
        return;
    }
    for ( choice ： The elements in this layer set （ The number of children in a tree is the size of the set ）) {
    
         Processing nodes ;
        backtracking( route , Selection list ); //  recursive 
         to flash back , Cancel processing result 
    }
}

This problem can be directly applied to the template of backtracking algorithm （ Picture transferred from code Capriccio ）

As for the for In the loop i <= n - (k - path.size()) + 1 Why do you write like this , You can see Reference article Explanation of pruning optimization department in .

This topic Java Code ：

class Solution {
    
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    private void backTracking(int n, int k, int start) {
    
        if (path.size() == k) {
    
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
    
            path.add(i);
            backTracking(n, k, i + 1);
            path.removeLast();
        }
    }
    public List<List<Integer>> combine(int n, int k) {
    
        backTracking(n, k, 1);
        return ans;
    }
}