回溯
解题思路
题干 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：只使用数字 1 到 9，每个数字 最多使用一次；
根据 leetcode🧑💻 39. 组合总和、leetcode🧑💻 40. 组合总和 II 的经验可知，只使用数字 1 到 9，每个数字 最多使用一次 可以给递归函数传递 inx 控制 for 循环的起点，从而避免出现 [2, 3] 和 [3, 2] 这样重复组合；
每次选择一个数 i 则
n -= i、k--，再利用 path 收集 i；终止条件：
n === 0 && k === 0说明找到满足条件的组合，将组合放入结果；剪枝：
- 如要要选择的数字
i > n则没有必要继续下去；- 如果
n < 0则没有必要继续下去；- 如果
k < 0则没有必要继续下去；
复杂度
-
时间复杂度:
O(n * 2^n)； -
空间复杂度:
O(n)；
代码实现
var combinationSum3 = function (k, n) {
let res = [];
backtrack(k, n, res, 1, []);
return res;
};
const backtrack = (k, n, res, inx, path) => {
if (n === 0 && k === 0) {
res.push([...path]);
return;
}
for (let i = inx; i <= 9; i++) {
if (i > n) return;
if (k < 0) return;
if (n < 0) return;
k--;
n -= i;
path.push(i);
backtrack(k, n, res, i + 1, path);
k++
n += i;
path.pop();
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 40. 组合总和 II
上一篇
评论
