216. Combination Sum III
216. Combination Sum III
题目
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers
1through9are 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 <= 91 <= 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;
};