#993 | 2022-04-02 18:18:45

组合总和 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
  }
}