Combination Sum with Unlimited Reuse
IMC Trading● MediumNEW GRADPHONE SCREENProblem statement
Given an integer array candidates and an integer target, return every distinct combination of candidate values whose sum equals target.
For this exercise, assume candidates contains distinct positive integers, each value may be reused any number of times, and a combination is identified by its multiset rather than its permutation. For this exercise, assume each returned combination is sorted in nondecreasing order and the list of combinations is lexicographically sorted; return an empty list when no combination exists.
Function
combinationSum(candidates: int[], target: int) → int[][]Examples
Example 1
candidates = [2,3,6,7]target = 7return = [[2,2,3],[7]]Reuse 2 twice with 3, or use 7 alone.
Example 2
candidates = [2,3,5]target = 8return = [[2,2,2,2],[2,3,3],[3,5]]These are the three distinct multisets totaling 8.
Example 3
candidates = [2]target = 1return = []The only available value exceeds the target.
Example 4
candidates = [7,2,3]target = 7return = [[2,2,3],[7]]The input order does not affect canonical output order.
Constraints
- For this exercise, assume
1 <= candidates.length <= 8. - For this exercise, assume all candidate values are distinct and satisfy
1 <= candidates[i] <= 40. - For this exercise, assume
1 <= target <= 30.