这是 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]]
关于「组合总和」的问题,之前我们已经完成过 39. 组合总和 和 40. 组合总和 II 两道题了。
只不过前面两道题是直接给了我们一个数组,让我们从数组中进行选择。
本题则是直接限定了数字范围在 1-9
之间。
三道题都是可以使用相同的思路进行求解。
我们再来强化一下应该如何快速判断一道题是否应该使用 DFS + 回溯算法来爆搜。
总的来说,你可以从两个方面来考虑:
到
,而 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 实现,但通常结合 DFS 来做,难度是最低的。
「回溯算法」根据当前决策有多少种选择,对应了两套模板。
void dfs(当前位置, 路径(当前结果), 结果集) {
if (当前位置 == 结束位置) {
结果集.add(路径);
return;
}
选择当前位置;
dfs(下一位置, 路径(当前结果), 结果集);
撤销选择当前位置;
dfs(下一位置, 路径(当前结果), 结果集);
}
对应到这类模板的题目有:40. 组合总和 II ...
void dfs(选择列表, 路径(当前结果), 结果集) {
if (满足结束条件) {
结果集.add(路径);
return;
}
for (选择 in 选择列表) {
做选择;
dfs(路径’, 选择列表, 结果集);
撤销选择;
}
}
对应到这类模板的题目有:17. 电话号码的数字组合、39. 组合总和 ...
这是我们「刷穿 LeetCode」系列文章的第 No.216
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
「在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。」