Choose, explore, undo — combination sum

1 · The problemA machine that wants exactly $7

An arcade machine has one rule: the prize is yours if you pay exactly seven dollars. No more, no less — it gives no change. You have four kinds of coins, worth $2, $3, $6 and $7, and as many of each as you want.

How hard could it be? Put coins in until the counter says seven.

2 · The obvious ideaThe first try, and the first undo

Start with a $2 coin. Then another: four. Another: six. Only one dollar is missing, and the next coin he reaches for is a $3. Six plus three is nine. Too much — and the machine does not give change, so this path is dead.

He does not empty the machine and start again. He takes back the last coin — just that one — and tries something else from there. This time he stops at two plus two and tries a $3: four plus three is exactly seven.

3 · The real questionOne answer isn't enough

Then he notices another way to win: a single $7 coin. And that changes the question. Finding one way to make seven was never the challenge. The challenge is finding every way.

"Every way" means you cannot stop at the first success, and you cannot trust luck to stumble on the rest. You need a way of trying things that is guaranteed to visit every possibility exactly once.

4 · The trapThe same answer, twice

Here is the second problem, and it is sneakier. Pay $2, then $3, then $2. That makes seven too. Is it a new answer?

No. It is the same combination as two, two, three — the same coins in your hand — picked in a different order. The machine does not care about order, and neither does the question. So now there are two problems at once:

1. Find every way

   Explore all the possibilities, missing none.

2. No repeats

   Never explore the same combination again in a different order.

Stated without the story: given a list of distinct positive numbers, the candidates, and a target, list every combination of candidates that adds up to the target. A candidate may be used any number of times. Two combinations that differ only in order count once. For candidates [2, 3, 6, 7] and target 7, the answer is [[2, 2, 3], [7]].

The question is how to make a computer explore all of that without losing itself.

5 · The structureEvery choice is a branch

Choose $2. From there you can choose $2 again, or $3, or $6, or $7. From each of those you have four choices again. Every choice creates another possible path, and every path offers more choices. Drawn out, the possibilities are a tree: the root is "nothing paid yet", each branch is a coin, and each point in the tree is the list of coins on the way down to it.

That tree grows quickly. Try everything blindly — any coin after any coin, stopping only when you reach or pass the target — and for $7 the tree already has 37 points to visit. If the machine wanted $40, it would have 6,757,745.

So the job is not "try everything". It is: walk this tree in a disciplined order, so that nothing is missed, nothing is visited twice, and branches that cannot work are left as early as possible.

6 · The moveUndo one step, not everything

Follow one path on the floor, a stone per coin. Two. Two. Two: six dollars paid, one left. Another $2 would make eight — past the target. And $3, $6 and $7 are even bigger, so none of them can work here either.

Now the important part. He does not throw everything away and walk back to the start. He undoes the last decision only — one step back — and he is at two, two again, with four dollars paid and the next choice untried. From there, $3 makes exactly seven.

Everything before the bad step was still useful. The first two coins did not cause the problem, so they stay.

7 · The nameThis is backtracking

He is not guessing at random. He is exploring a tree of decisions, with three moves:

1. Choose

   Pick a coin and add it to the path.

2. Explore

   Go on from there: everything that choice can lead to.

3. Undo

   When that is finished — success or dead end — take the coin back and try the next one.

That is backtracking: build a solution one choice at a time, explore it, and when the path fails, go back and try another choice. It doesn't mean starting over every time something fails — that is the whole point. You keep the choices that are still useful and only undo the one you need to change.

If you have read the Sudoku solver, this is the same loop with coins instead of digits: the digit lifted off the board there is the coin taken back here.

8 · The second ruleThe gate: never go back to an earlier coin

Choose, explore, undo finds every way. It also finds [2, 3, 2] and [3, 2, 2] and [2, 2, 3] — the same combination three times. Remember why: after choosing $3, he allowed himself to go backward to $2.

So add one rule. Put the coins in a fixed order — 2, 3, 6, 7 — and once you have moved forward to a coin, you never go back to an earlier one. Like a one-way gate.

The rule only forbids going backward. Staying is allowed: after choosing $2 you can choose $2 again, because you are not moving past it. That is how a coin is used more than once.

Why does this kill the duplicates without losing any answer? Because every combination has exactly one way of being written with its coins in non-decreasing order: [2, 2, 3], never [2, 3, 2]. The gate makes that the only order the search can produce, so each combination is built once.

9 · The codeThe code, one action at a time

Nothing magical happens in the code. It copies what he did on the floor, one action per line. First, the two things he carries: the answers found so far, and the path — the coins in his backpack right now.

class Solution:    def combinationSum(self, candidates, target):        result = []        path = []

The function that explores

One function, backtrack, does the walking. It needs to know two things: where it may start choosing from (the gate), and how much of the target is still left.

        def backtrack(start, remaining):

When the path is an answer

If nothing is left to pay, the path adds up to the target. Save it and stop exploring this branch — any coin added now would pass the target.

        def backtrack(start, remaining):            if remaining == 0:                result.append(path[:])                return

Try every coin you are allowed to choose

Otherwise, go through the candidates — but only from start onward. That is the gate in code: the loop never looks at a coin before start, so it can never go backward.

            for i in range(start, len(candidates)):                if candidates[i] > remaining:                    break

Stop when the coin is too big

If the current coin is already bigger than what is left, every coin after it is bigger too — if the coins are in order. So the very first thing the function does is sort them, and then a too-big coin can end the loop with break instead of checking the rest.

        candidates.sort()

            for i in range(start, len(candidates)):                if candidates[i] > remaining:                    break

Choose

Make the choice by adding the coin to the path. That is the coin picked up and dropped in the backpack.

                path.append(candidates[i])

Explore

Then call backtrack again: one level deeper into the tree, with the coin just chosen subtracted from what is left.

                path.append(candidates[i])                 backtrack(                    i,                    remaining - candidates[i]                )

Look at the first argument. It is i, not i + 1. The next call may start choosing from the same coin — that is "stay on the same pad". Pass i + 1 and the search would move past the $2 the moment it chose one, and [2, 2, 3] could never be built.

Undo

And the most important line. When the deeper exploration is finished — whether it found answers or hit a dead end — remove the last choice.

                path.append(candidates[i])                 backtrack(                    i,                    remaining - candidates[i]                )                 path.pop()

path.pop() is him walking backward one stone. Without it, the coin would still be in the backpack when the loop tries the next coin, and the path would only ever grow.

Start it, and return the answers

The first call starts at the first coin with the whole target still to pay.

        backtrack(0, target)         return result

The whole thing

class Solution:    def combinationSum(self, candidates, target):        result = []        path = []         candidates.sort()         def backtrack(start, remaining):            if remaining == 0:                result.append(path[:])                return             for i in range(start, len(candidates)):                if candidates[i] > remaining:                    break                 path.append(candidates[i])                 backtrack(                    i,                    remaining - candidates[i]                )                 path.pop()         backtrack(0, target)         return result

Three lit lines, three moves: line 17 chooses, lines 19–22 explore, line 24 undoes. The loop around them tries the next choice.

If you remember nothing else, remember the physical story:

In the story	In the code
The coins in my backpack	path
The cards on the wall	result
Exactly seven: an answer	if remaining == 0: result.append(path[:])
The one-way gate	for i in range(start, …)
Too high, and every bigger coin too	if candidates[i] > remaining: break
I pick up a coin	path.append(candidates[i])
I walk deeper, on the same pad if I like	backtrack(i, remaining - candidates[i])
I walk backward	path.pop()
I try the next branch	the next turn of the for loop

10 · The real runEvery move the program makes

Here is the program above, run on [2, 3, 6, 7] and 7, every event in order. "Choose" is line 17, "undo" is line 24, "too big" is the break on line 15.

#	What happens	Path after it	Left

Count them: 9 choices, 9 undos, 10 calls, and two answers. Every coin that went into the backpack came back out — that is what lets the next branch start clean.

11 · The costWhat it costs

The two rules are not only about correctness. Each one cuts the tree. Count the calls to backtrack — the points of the tree the program actually visits:

Search	Target 7	Target 40	Answers for 40
Blind: any coin after any coin	37	6,757,745	748,874 (with every order)
With the gate (start)	28	1,484	77
With the gate, sorted, with break	10	973	77

The gate is the big one. It turns 748,874 ordered sequences into the 77 combinations that were actually asked for, and the tree shrinks with them — from almost seven million calls to under fifteen hundred. The sort and the break then stop every branch at the first coin that is too big instead of trying each bigger coin and failing.

Time: exponential in the worst case — the number of combinations itself can grow exponentially with the target, and the program has to build each one. A common bound is O(N^T/M) for N candidates, target T and smallest candidate M: the tree is at most T/M levels deep with at most N branches per point. Space: O(T/M) for the path and the call stack — the deepest path is all smallest coins — plus the answers themselves.

That is the usual shape of backtracking: you cannot avoid walking the tree, so the craft is in making the tree smaller — rules that refuse a branch as early as possible.

12 · Try itYour own coins, your own target

Things to try: switch the gate off and watch [2, 3, 2] and [3, 2, 2] appear in red. Switch the break off and watch the program walk into $8 and $9 before turning back. Then put both back and set the target to 40.

13 · The bigger ideaWhat if order mattered?

Backtracking shows up wherever a problem asks you to explore a huge number of choices: a Sudoku, placing queens on a chessboard, finding a way through a maze, listing every order of a few things. The structure is the same each time: choose something, explore what happens, and if the path can't work, undo the choice and try another.

So try this before you go: in this problem, [2, 3, 2] is the same answer as [2, 2, 3]. What if order suddenly mattered? Then [2, 2, 3], [2, 3, 2] and [3, 2, 2] are three different answers, and two answers become four.

Which line of the program would you change? (Hint: the gate. With the gate off, the lab above already counts the four.)

14 · PracticeFour problems, same shape

For each one, write down the three answers — the choices, the failure, the undo — and the rule that stops repeats, before touching the keyboard.

• Warm-upSubsets

  List every subset of a few distinct numbers. Every point of the tree is an answer, not only the leaves. Where does the "save a copy" line go now?

• PracticeCombination sum, from scratch

  Close this page and write it yourself. Then switch the gate off in your own code and check that you get four answers for 7 — and 6,757,745 calls for 40 if you also drop the sort and the break.

• VariationEach coin only once

  The pile now has a fixed set of coins, some of them equal (say 1, 1, 2, 5, 6, 7, 10), and each can be used once. Two changes: what is the next call's start, and how do you stop the two 1s from producing the same combination twice?

• ChallengePermutations

  Every order of a few distinct numbers. The gate is gone — order matters now — so what stops you from using the same number twice in one path?

Choose. Explore. Undo. Then try the next one.