How do you solve combination sum, where each candidate may be used more than once?
You use backtracking. You pick a candidate, you take it away from what is left to reach, and you call yourself again with the same candidate still available.
def combination_sum(candidates, target):
results = []
def backtrack(start, remaining, current):
if remaining == 0:
results.append(list(current))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
continue
current.append(candidates[i])
backtrack(i, remaining - candidates[i], current)
current.pop()
backtrack(0, target, [])
return results
So how does it work? The function has three pieces of state. The start says which candidates you are allowed to look at. The remaining says how much is still needed. And the current list holds the candidates that have been chosen so far.
When the remaining reaches zero you have found an answer, so you save a copy of the current list and you stop. Otherwise you go through the candidates from the start position onwards. For each one that is small enough you add it to the current list and you call yourself again with the remaining amount reduced and with the start position set to that same candidate, which is what allows the candidate to be used more than once.
And the two details that matter are these. The start position moves forward as you choose, so the same group of candidates is never built in a different order. And the pop at the end of the loop takes the candidate back out, so the next choice starts from the same place.
And the answer for the candidates [2, 3, 6, 7] and the target 7 is [[2, 2, 3], [7]]. And the complexity is hard to write down as a single formula, because it depends on the numbers. In general it is proportional to the number of answers and to the work done on the way to each one.
So the rule to remember is this. The start position says what you may still choose, and keeping it the same after a choice is what lets a candidate be used again.
The last question in this topic shows the version where each candidate is used at most once.