What the start index controls

One number in the recursive call decides whether items can repeat and whether orderings count separately.

Key idea

The index in the recursive call

In a loop-over-choices search, what you pass as the next start index decides the entire character of the problem. Three values, three meanings, and confusing them is the source of most wrong answers in this unit.

Recursive call	Meaning	Result
explore(index + 1)	move past this item	each item used at most once, combinations
explore(index)	this item may be reused	unlimited repeats, combinations
explore(0)	every item available again	orderings counted separately, permutations

The same function with only that one argument changed produces genuinely different answers.

1def ways_to_total(parts, target, allow_reuse):2    results, current = [], []3 4    def explore(start, remaining):5        if remaining == 0:6            results.append(current[:])7            return8        for index in range(start, len(parts)):9            if parts[index] > remaining:10                continue11            current.append(parts[index])12            explore(index if allow_reuse else index + 1, remaining - parts[index])13            current.pop()14 15    explore(0, target)16    return results17 18print(ways_to_total([1, 2, 3], 4, True))19print(ways_to_total([1, 2, 3], 4, False))

Quick check· 5 min

Which index does this need?

You must list every way to make change for an amount using given coin values, where each coin may be used any number of times, and where [1, 3] and [3, 1] count as the same way. What should the recursive call pass?

The current index, so the same coin can be picked again while still forcing non-decreasing orderThe current index plus one, so each coin is used at most onceZero, so every coin is available at every levelThe current index plus one, after sorting the coins descending

Problem· 25 min

Combination Sum

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def ways_to_total(parts, target, allow_reuse):2 results, current = [], []3 4 def explore(start, remaining):5 if remaining == 0:6 results.append(current[:])7 return8 for index in range(start, len(parts)):9 if parts[index] > remaining:10 continue11 current.append(parts[index])12 explore(index if allow_reuse else index + 1, remaining - parts[index])13 current.pop()14 15 explore(0, target)16 return results17 18print(ways_to_total([1, 2, 3], 4, True))19print(ways_to_total([1, 2, 3], 4, False))