算法训练Day24|理论基础 ● 77. 组合

1// 回溯函数返回值及参数
2void backtracking(参数)
3

1// 回溯函数终止条件
2void backtracking(参数)
3

 1void backtracking(参数) {
 2    if (终止条件) {
 3        存放结果;
 4        return;
 5    }
 6
 7    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
 8        处理节点;
 9        backtracking(路径，选择列表); // 递归
10        回溯，撤销处理结果
11    }
12}

 1class Solution {
 2    List<List<Integer>> result = new ArrayList<>(); // 存放最终结果集  
 3    LinkedList<Integer> path = new LinkedList<>(); // 存放每条路径的结果
 4
 5    public List<List<Integer>> combine(int n, int k) {
 6        combineHelper(n, k, 1);
 7        return result;
 8    }
 9    // 确定回溯函数递归逻辑
10    private void combineHelper(int n, int k, int startIndex) {
11        // 确定终止条件：当path中的个数等于k时加入到结果集result中
12        if (path.size() == k) {
13            result.add(new ArrayList<>(path));
14            return;
15        }
16        // for循环进行横向遍历
17        for (int i = startIndex; i < n - (k - path.size()) + 1; i++) {
18            path.add(i);
19            // 递归进行深度遍历
20            combineHelper(n, k, i + 1); // i + 1 代表表示递归遍历的层数
21            path.removeLast();
22        }
23    }
24}