Pattern
Pattern
Pattern
Explore choices recursively, undoing each choice before trying the next.
Choose, recurse, unchoose; prune invalid partial states early.
path = []
answers = []
def backtrack(start, remaining):
if remaining == 0:
answers.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, remaining - candidates[i])
path.pop()