LeetCode: Combination Sum Solution

Approach

Exhausively try all the cases

combination: store the list of candidates for each check

remaining: check whether a combination sum equals to target

Implementation

1var combinationSum = function (candidates, target) {
2  const res = []
3
4  const recursion = ({ candidates, remaining, combination }) => {
5    if (remaining < 0) {
6      return
7    }
8    if (remaining === 0) {
9      res.push(combination)
10      return
11    }
12    candidates.forEach((candidate, i) =>
13      recursion({
14        candidates: candidates.slice(i), // a candidate could be reused
15        remaining: remaining - candidate,
16        combination: [...combination, candidate],
17      })
18    )
19  }
20
21  recursion({ candidates, remaining: target, combination: [] })
22
23  return res
24}

References

Original problem

Similar problems

Letter Combinations of a Phone Number

Combination Sum II

Combinations

Combination Sum III

Factor Combinations

Combination Sum IV