题目:
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
输入: k = 3, n = 7
输出: [[1,2,4]]
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
抛砖引玉
这个月是组合月吗,和递归回溯杠上了(¬_¬)瞄
思路
递归回溯的逻辑不变
更新约束条件:
实现
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
let _result = []
if (k === 0) return _result
function dfs(i, item, sum) {
if (item.length + (n - i + 1) < k || sum > n || i > 10) return
if (item.length === k && sum === n) {
_result.push(item)
return
}
dfs(i + 1, [...item, i], sum + i)
dfs(i + 1, item, sum)
}
dfs(1, [], 0)
return _result
}
修改约束条件:
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
let _result = []
function helper(i, item, sum) {
if (item.length > k) return
if (sum === n && item.length === k) {
_result.push(item)
return
}
for (let x = i; x < 10; x++) {
if (n - sum - x >= 0 && item.length < k) {
item.push(x)
helper(x + 1, [...item], sum + x)
item.pop()
}
}
}
helper(1, [], 0)
return _result
}