组合总和 2
在所有 JavaScript 提交中击败了 95.94%
的用户
这可能是我最好成绩了……
// 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的每个数字在每个组合中只能使用 一次 。
// 注意:解集不能包含重复的组合。
// console.log(combinationSum2([10,1,2,7,6,1,5], 8))
function combinationSum2 (candidates, target) {
const len = candidates.length
if (!len) return []
const results = []
const nums = candidates.slice()
nums.sort((a, b) => a - b)
let sum = 0
const q = []
walk(0)
return results
function walk (start) {
if (sum === target) {
results.push(q.slice())
return false
} else if (sum > target) {
return false
}
for (let i = start; i < len; i++) {
if (i > start && nums[i] === nums[i - 1]) continue
const v = nums[i]
q.push(v)
sum += v
const should_continue = walk(i + 1)
sum -= v
q.pop()
if (!should_continue) break
}
return true // should continue
}
}