Backtracking · 082Medium
Combination Sum
Given an array of DISTINCT integers candidates and a target, return all unique combinations summing to target. Each candidate may be used unlimited times. Two combinations are the same if they contain the same numbers with the same counts.
Constraints
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- 1 <= target <= 40
- All candidates are distinct.
Examples
combinationSum([2, 3, 6, 7], 7) -> [[2, 2, 3], [7]] combinationSum([2, 3, 5], 8) -> [[2,2,2,2], [2,3,3], [3,5]] combinationSum([2], 1) -> [] combinationSum([2, 3, 5], 3) -> [[3]] // one candidate, used once combinationSum([2], 6) -> [[2, 2, 2]] // the only candidate, reused combinationSum([2, 4], 7) -> [] // even candidates never sum to an odd target
Edge cases
- Candidates may repeat within one combination.
- [2,2,3] and [2,3,2] are the SAME combination.
- No valid combination returns an empty array.
Show the target complexity (spoiler)
- Naive
- Recursing over all candidates at every level generates permutations, then needs de-
- Target
- Backtracking with a start index and a remaining target, pruning as soon as remaining goes negative.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/082-combination-sum.js ./practice c 082