LeetCode: Combination Sum II Solution

Backtracking with duplication check

Implementation

1var combinationSum2 = function (candidates, target) {
2  const res = []
3
4  const recursion = ({ candidates, remaining, combination }) => {
5    if (remaining < 0) return
6
7    if (remaining === 0) {
8      res.push(combination)
9      return
10    }
11
12    candidates.forEach((candidate, i) => {
13      if (i > 0 && candidate === candidates[i - 1]) return // duplication check
14
15      recursion({
16        candidates: candidates.slice(i + 1), // a candidate must not be reused
17        remaining: remaining - candidate,
18        combination: [...combination, candidate],
19      })
20    })
21  }
22
23  candidates.sort() // to help detect duplication while backtracking
24
25  recursion({
26    candidates,
27    remaining: target,
28    combination: [],
29  })
30
31  return res
32}