Combination Sum
MediumBacktracking
Given an array of distinct positive integers candidates and a positive integer target, return every combination of candidates whose values add up to target.
- The same candidate may be used any number of times.
- A combination is a multiset: two combinations are the same if they use each value the same number of times, regardless of order. Return each combination only once.
- Return the combinations in any order; the values inside a combination may also be in any order.
- If no combination works, return an empty list.
The inputs are chosen so that fewer than 150 combinations exist.
Example 1
- Input:
- candidates = [2,4,6], target = 8
- Output:
- [[2,2,2,2],[2,2,4],[2,6],[4,4]]
- Explanation
- Using 2 four times, 2 twice plus 4, 2 plus 6, or 4 twice all reach 8.
[4,2,2]would be the same combination as[2,2,4], so it is not listed again.
Example 2
- Input:
- candidates = [3,5,8], target = 11
- Output:
- [[3,3,5],[3,8]]
- Explanation
- 3 + 3 + 5 = 11 and 3 + 8 = 11. No combination using 5 twice works.
Example 3
- Input:
- candidates = [2,4], target = 5
- Output:
- []
- Explanation
- Every candidate is even, so no combination can add up to an odd target.
Constraints
1 <= candidates.length <= 302 <= candidates[i] <= 40- All values in
candidatesare distinct 1 <= target <= 40