Combination Sum II
MediumP2Coding
A shop sells candies with the prices in costs (prices may repeat, and each candy can be bought at most once). You have target coins and want to spend all of them.
Return every distinct combination of prices that sums to target. Two combinations are the same if they hold the same prices the same number of times. Write each combination in increasing order and list the combinations in lexicographic order. If there is none, return an empty array.
Example 1
- Input
- costs = [10,1,2,7,6,1,5], target = 8
- Output
- [[1,1,6],[1,2,5],[1,7],[2,6]]
- Why
- Four distinct combinations; note [1,1,6] uses both 1s.
Example 2
- Input
- costs = [2,5,2,1,2], target = 5
- Output
- [[1,2,2],[5]]
Example 3
- Input
- costs = [], target = 3
- Output
- []
Constraints
- 0 <= costs.length <= 100
- 1 <= costs[i] <= 50
- 1 <= target <= 100
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.