Combinations That Sum
Problem
Given a list of distinct positive numbers and a target, return every group of them that adds up exactly to the target. A number may be used as many times as you like, and two groups holding the same numbers in a different order count as one answer.
Examples
Input: nums = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Why: 2 + 2 + 3 and 7 on its own; 3 + 2 + 2 is the same groupInput: nums = [2], target = 4
Output: [[2, 2]]
Why: the same number may be reusedInput: nums = [3, 5], target = 4
Output: []
Why: edge case, no combination of 3 and 5 lands on 4Hints
0 / 3
Counting each group once means the branches at each level must never look backwards. Decide what a branch is allowed to pick before writing the loop.
Track how much of the target is still left rather than what has been spent, and the base case becomes a single comparison with zero.
Recurse with a start index. A branch may reuse the value it just picked, so recurse with the same index rather than the next one. Sorting first lets the loop stop the moment a value exceeds the remainder.
Solution
Recurse with a start index so a branch never revisits earlier values, which is what stops a group being reported in several orders. The remaining target shrinks on the way down, and hitting zero records a copy of the path. Sorting first turns the impossible branches into a single break: once a value is larger than what is left, so is every value after it. Time is exponential in the worst case, bounded by the number of valid groups times the target divided by the smallest value; recursion depth is that same ratio.
def combos(nums, target):
out = []
nums.sort()
def build(start, left, path):
if left == 0: # target hit exactly
out.append(path[:])
return
for i in range(start, len(nums)):
if nums[i] > left: # sorted, so nothing later fits
break
path.append(nums[i])
build(i, left - nums[i], path) # i, not i+1: a value may repeat
path.pop()
build(0, target, [])
return out
print(combos([2, 3, 6, 7], 7)) # -> [[2, 2, 3], [7]]
print(combos([2], 4)) # -> [[2, 2]]
print(combos([3, 5], 4)) # -> []Stuck on the idea rather than the code? Subsets covers it.