Write combination_sum(candidates, target) that returns every combination of values from candidates whose sum is exactly target.
candidatesholds distinct positive integers (2 to 40);1 <= target <= 40;1 <= len(candidates) <= 30.- Each candidate may be used any number of times.
- Two combinations are the same if they use the same values the same number of times, so
[2, 3, 2]and[2, 2, 3]count once. Return each combination once, in any order, with its values in any order. - Return
[]if nothing works.
combination_sum([3, 5, 2], 8) # [[3, 5], [3, 3, 2], [2, 2, 2, 2]] in some order
combination_sum([4, 6], 3) # []
Produce each combination exactly once: at the largest sizes there are tens of millions of orderings, so generating them and removing duplicates is far too slow.
Show hint
duplicates come from choosing the same values in a different order. Fix an order on the candidates and never pick one that comes before the last one you picked (picking the same one again is fine).