【回溯算法】77. 组合

77. 组合

解题思路

• 回溯结束条件 track长度等于k 然后收集当前的路径
• 遍历所有的节点 然后选择当前节点 通过start参数控制遍历 避免产生重复的子集
• 移除当前的选择

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

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

    void backtrack(int start,int n,int k){
        if(k == track.size()){
            // 当前回溯结束  收集当前记录
            res.add(new LinkedList<>(track));
            return;
        }

        // 回溯算法标准框架
        for(int i = start; i <= n; i++){
            // 路径 选择当前节点
            track.addLast(i);
            // 通过start参数控制树枝的遍历  避免产生重复的子集
            backtrack(i + 1, n,k);
            track.removeLast();// 移除当前选择
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27