Combination Sum II
MediumBacktracking
Given an array of positive integers candidates (which may contain repeated values) and a positive integer target, return every distinct combination of elements whose values add up to target.
- Each element may be used at most once, so a value can appear in a combination at most as many times as it appears in
candidates. - Combinations are compared as multisets of values: two combinations that use the same values the same number of times count as one, even if they were built from different positions. Return each 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.
Example 1
- Input:
- candidates = [1,2,1,3,2], target = 4
- Output:
- [[1,1,2],[1,3],[2,2]]
- Explanation
- 1 + 1 + 2 uses both 1s, 2 + 2 uses both 2s, and 1 + 3 is the last option. Picking the first 1 or the second 1 with 3 gives the same combination, so
[1,3]appears once. 1 + 1 + 1 + 1 is impossible because there are only two 1s.
Example 2
- Input:
- candidates = [3,4,5], target = 2
- Output:
- []
- Explanation
- Every candidate is already larger than the target.
Example 3
- Input:
- candidates = [4,4,4,8], target = 8
- Output:
- [[4,4],[8]]
- Explanation
- Two 4s or the single 8. Three different pairs of 4s exist, but they all form the same combination.
Constraints
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30