Medium Backtrack+Prune Backtracking
In plain English: Find all ways to pick numbers from a list (reuse allowed) that add up to a target sum.
Like combinations, but allow reuse by not advancing the start index. Prune when the remaining target goes negative.
Prompt
Given an array of distinct integers (candidates) and a target, find all unique combinations that sum to the target. Each number may be reused unlimited times.
Try to write it from scratch before scrolling down.
Solution
def combination_sum(candidates, target):
result = []
candidates.sort()
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # prune: sorted, so all subsequent are too large
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, not i+1: reuse allowed
path.pop()
backtrack(0, [], target)
return result
# Test: combination_sum([2,3,6,7], 7) == [[2,2,3],[7]]