noodleProblems/
Combination Sum
#48

Combination Sum

AlgorithmmediumArrayBacktracking

Given an array of **distinct** integers candidates and a target integer target, return every unique combination of candidates that sums to target.

The **same** candidate may be chosen an unlimited number of times. Two combinations are the same if one is a reordering of the other, so each distinct multiset of numbers must appear at most once.

You may return the combinations in any order, and the numbers within each combination in any order — any valid arrangement is accepted.

Example cases

  • reuse allowed
    in candidates = [2,3,6,7], target = 7
    out [[2,2,3],[7]]
    2 + 2 + 3 = 7 and 7 = 7. 2 may be reused.
  • multiple combos
    in candidates = [2,3,5], target = 8
    out [[2,2,2,2],[2,3,3],[3,5]]
  • no solution
    in candidates = [2], target = 1
    out []
    No multiple of 2 reaches the odd target 1.

Constraints

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40
Saved
candidates =
[2,3,6,7]
target =
7