Combination sum: reach a target with reusable values
Coding problemMediumAsked in: Adobe, Amazon, Microsoft, NPCI
Given a list of distinct positive integers candidates and a positive integer target, find every combination of candidates whose values add up to target. A candidate may be used any number of times in a combination.
Two combinations are the same when they use each candidate the same number of times, so [2, 2, 3] and [3, 2, 2] count once. Return the combinations in any order; the values inside a combination may be in any order too. If none exists, return an empty list.
Examples
Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3
Input: candidates = [2], target = 1
Output: []
Constraints
- The list holds between 1 and 30 distinct candidates
- Each candidate is between 2 and 40
- target is between 1 and 40
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.