题目描述
这是 LeetCode 上的216. 组合总和 III，难度为 Medium。
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 复制代码
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 复制代码
DFS + 回溯解法
关于组合总和的问题，之前我们已经完成过 39. 组合总和 和 40. 组合总和 II 两道题了。
只不过前面两道题是直接给了我们一个数组，让我们从数组中进行选择。
本题则是直接限定了数字范围在 1-9 之间。
三道题都是可以使用相同的思路进行求解。
我们再来强化一下应该如何快速判断一道题是否应该使用 DFS + 回溯算法来爆搜。
总的来说，你可以从两个方面来考虑：
- 1. 求的是所有的方案，而不是方案数。 由于求的是所有方案，不可能有什么特别的优化，我们只能进行枚举。这时候可能的解法有动态规划、记忆化搜索、DFS + 回溯算法。
- 2. 通常数据范围不会太大，只有几十。 如果是动态规划或是记忆化搜索的题的话，由于它们的特点在于低重复/不重复枚举，所以一般数据范围可以出到 10510^5105 到 10710^7107，而 DFS + 回溯的话，通常会限制在 30 以内。
这道题数据范围是 30 以内，而且是求所有方案。因此我们使用 DFS + 回溯来求解：
class Solution { int n, k; public List<List<Integer>> combinationSum3(int _k, int _n) { n = _n; k = _k; List<List<Integer>> ans = new ArrayList<>(); List<Integer> cur = new ArrayList<>(); dfs(1, ans, cur, 0); return ans; } /** * u: 当前遍历到的数字 * ans: 最终结果集 * cur: 当前结果集 * sum: 当前结果集的总和 */ void dfs(int u, List<List<Integer>> ans, List<Integer> cur, int sum) { if (sum == n && cur.size() == k) { ans.add(new ArrayList<>(cur)); return; } if (u == 10 || sum > n || cur.size() > k) return; // 使用数字 u cur.add(u); dfs(u + 1, ans, cur, sum + u); // 进行回溯 cur.remove(cur.size() - 1); // 不使用数字 u dfs(u + 1, ans, cur, sum); } } 复制代码
- 时间复杂度： DFS 回溯算法通常是指数级别的复杂度（因此数据范围通常为 30 以内）。这里暂定 O(n∗2n)O(n * 2^n)O(n∗2n)
- 空间复杂度：同上。复杂度为 O(n∗2n)O(n * 2^n)O(n∗2n)
总结
一连三天，我们做了三道关于组合总和的题目。
但其实并无本质区别，都是在考察「回溯算法」的基本使用。
对于此类要枚举所有方案的题目，我们都应该先想到「回溯算法」。
「回溯算法」从算法定义上来说，不一定要用 DFS 实现，但通常结合 DFS 来做，难度是最低的。
「回溯算法」根据当前决策有多少种选择，对应了两套模板。
- 每一次独立的决策只对应 选择 和 不选 两种情况：
- 确定结束回溯过程的 base case
- 遍历每个位置，对每个位置进行决策（做选择 -> 递归 -> 撤销选择）
void dfs(当前位置, 路径(当前结果), 结果集) { if (当前位置 == 结束位置) { 结果集.add(路径); return; } 选择当前位置; dfs(下一位置, 路径(当前结果), 结果集); 撤销选择当前位置; dfs(下一位置, 路径(当前结果), 结果集); } 复制代码
对应到这类模板的题目有：40. 组合总和 II ...
- 每一次独立的决策都对应了多种选择（通常对应了每次决策能选择什么，或者每次决策能选择多少个 ...）:
- 确定结束回溯过程的 base case
- 遍历所有的「选择」
- 对选择进行决策 (做选择 -> 递归 -> 撤销选择)
void dfs(选择列表, 路径(当前结果), 结果集) { if (满足结束条件) { 结果集.add(路径); return; } for (选择 in 选择列表) { 做选择; dfs(路径’, 选择列表, 结果集); 撤销选择; } } 复制代码
对应到这类模板的题目有：17. 电话号码的数字组合、39. 组合总和 ...
最后
这是我们「刷穿 LeetCode」系列文章的第 No.216 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
