216. 组合总和 III
216. 组合总和 III
题目
Find all valid combinations of k
numbers that sum up to n
such that the following conditions are true:
- Only numbers
1
through9
are used. - Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.
Constraints:
2 <= k <= 9
1 <= n <= 60
题目大意
找出所有相加之和为 n
的 k
个数的组合,且满足下列条件:
- 只使用数字
1
到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
解题思路
可以通过回溯算法和递归找到所有满足给定条件的组合:
- 定义结果数组
res
用于存储符合条件的组合,以及路径数组track
用于暂时存储当前组合的数字。 - 使用
backtrack
函数进行递归搜索,其中start
参数表示搜索的起始数字,保证每个数字最多使用一次。 - 在递归的过程中,判断当前组合的长度是否等于
k
且组合的和是否等于目标值n
,如果满足条件,则将当前组合加入结果数组。 - 在递归的过程中,进行剪枝:
- 如果当前组合的和超过目标值
n
,则直接返回,因为后续的数字只会更大,无法满足条件。 - 如果当前组合的长度超过
k
,则直接返回,因为组合中的数字过多。
- 如果当前组合的和超过目标值
- 循环遍历数字
i
,将其加入当前组合,并更新组合的和。然后递归调用backtrack
函数,并在递归完成后将数字i
弹出组合,同时更新组合的和,以便回溯到上一层。 - 最终返回结果数组
res
。
代码
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function (k, n) {
let res = [];
let track = [];
let sum = 0;
const backtrack = (start) => {
// 找到一个满足条件的组合
if (track.length == k && sum == n) {
res.push([...track]);
return;
}
// 当前组合的和超过 n ,剪枝
if (sum > n) {
return;
}
// 当前组合的长度超过 k ,剪枝
if (track.length > k) {
return;
}
for (let i = start; i <= 9; i++) {
track.push(i);
sum += i;
backtrack(i + 1);
track.pop();
sum -= i;
}
};
backtrack(1);
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
39 | 组合总和 | [✓] | 数组 回溯 | 🟠 | 🀄️ 🔗 |