Expert · Backtracking · 233 of 264
Combination sum
Print every combination of the given numbers (each number may be used several times) that adds up to the target. Write each combination in ascending order; print the combinations in ascending (dictionary) order of their numbers.
Input: different positive whole numbers on one line, then the target (up to 40). Output: one combination per line, or none
Examples
2 3 6 7 7
2 2 3 7
2 3 5 8
2 2 2 2 2 3 3 3 5
4 3
none
One more test checks other inputs when you press Check.
Stuck? The idea behind backtracking
Build an answer one choice at a time; when a choice leads nowhere, undo it and try the next. Recursion keeps track of where you are.
Check as early as you can whether a partial answer can still work, so dead ends are left quickly.
def subsets(items, chosen=[]):
if not items:
print(chosen)
return
subsets(items[1:], chosen + [items[0]])
subsets(items[1:], chosen)
subsets([1, 2])Watch for: Changing a shared list without undoing the change afterwards leaves the next choice with the wrong start.