前言

回溯和动态规划是我最害怕的算法，这次我要直面恐惧

架构

  1. 主函数调用回溯函数
  2. 不递归传递结果，直接记录到全局变量中
  3. 做 - 递归 - 回撤 这个逻辑放到 for 循环中

例子

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字 1 到 9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

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
28
29
30
31
32
33
34
35
class Solution {
    // 结果和过程直接放到全局，不用考虑递归时的传递
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();

    // 主函数只用调用一次回溯即可
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k, n, 1);
        return res;
    }

    private void backtrack(int k, int n, int start){
        // 递归终止条件
        if(path.size() == k){
            if(n == getSum()){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        // 做 - 递归 - 回撤 放到 for 循环中
        for(int i = start; (i < 10 - (k - path.size()) + 1) && n > getSum(); i++){
            path.add(i);
            backtrack(k, n, i + 1);
            path.removeLast();
        }
    }

    private int getSum(){
        int sum = 0;
        for(int i = 0; i < path.size(); i++){
            sum += path.get(i);
        }
        return sum;
    }
}

剪枝

循环中没用的直接去除，像上面的例子中，(i < 10 - (k - path.size()) + 1) && n > getSum() 就是剪枝。

剪枝不用你手动去写逻辑代码，只需要一些终止条件即可。

其余

不知道怎么去除末尾，使用 LinkedList.removeLast()