leetcode 216. 组合总和 III

---

---

题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思考

• 1、和leetcode 77 组合题基本一致，就是我们循环递归的个数现在不是n来控制，而是就是9个嵌套
• 2、题目要求我们需要总和，那么我们在递归函数中就需要定义一个sum，因为我们每次的值是不一样
• 3、我们在回溯中不仅要将上一个元素弹出，去匹配另外一个树枝，并且需要重新计算sum值

代码和注释

class Solution {
    // 收集路径
    LinkedList<Integer> path = new LinkedList<>();
    // 结果集
    List<List<Integer>> result = new ArrayList<>();

    /**
        使用回溯法
        1、函数的参数
        2、终止条件按
        3、每轮递归干的事
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtacking(k, n, 0, 1);
        return result;
    }

    // 回溯函数 sum 是已经收集的总和
    public void backtacking(int k, int n,int sum, int startIdx){
        // 1、结束条件
        if(path.size() == k){
            // 当前和与目标和一致的时候需要收集结果
            if(sum == n){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        // 2、每轮递归回溯要干的事（剪枝）
        for(int i = startIdx; i <= 9-(k - path.size()) + 1; i++){
            sum +=i;
            path.add(i);
            // 开始的下标向后走
            backtacking(k, n, sum, i + 1);
            // 回溯
            path.removeLast();
            sum -= i;
        }
    }
}
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
36
37
38
39

总结

• 1、回溯递归三部曲
  • a:定义递归函数的参数
  • b：终止条件【大多数为path集合深度和目标长度一致返回，加一个目标结果收集】
  • c:每轮递归要干嘛【业务+最后回溯】
• 2、优化剪枝：总长-（目标长度-收集的长度）【其实这里我们考虑的就是至多递归到的位置，然后我们收集的长度有没有到目标长度】