Backtracking & Exact-Length Mixes
Tunebox Radio has a 7-minute gap before the news, and dead air isn't an option. The DJ doesn't want a mix that fills it exactly. They want every one, to pick from. No formula lists them. You have to try choices, but try them systematically, and drop a branch the moment it can't work. That's backtracking.
Choose, explore, un-choose
Every backtracking function has the same three beats at its heart. Make a choice. Recurse to explore everything that follows from it. Then undo the choice, so the next option starts from a clean slate.
path is one list shared by every call. start makes sure we only ever
add tracks after the last one chosen. That's why ["Blink", "Aurora"] never
shows up as a second copy of ["Aurora", "Blink"].
Step through a two-track version and watch path grow and shrink:
❓ Cross-question: "Why
path[:]and not justpath?"pathis one list that keeps changing. Appendingpathitself stores a reference to it, so every entry inoutis the same list, and it's empty by the time the search ends.path[:]stores a snapshot.
This should print all four subsets of ["a", "b"]. It prints four empty lists. Make each recorded subset keep its contents.
The recursion tree and its cost
Draw each call as a node and each loop step as an edge to a child. For three tracks you get:
[]
/ | \
[A] [B] [C]
/ \ |
[A,B] [A,C] [B,C]
|
[A,B,C]Every subset is exactly one node. Each track is in or out, so n tracks give 2ⁿ nodes, and each copy costs up to n: O(n · 2ⁿ). One more track doubles the work, so backtracking is for small n or heavily pruned trees.
def count_nodes(n, start=0):
return 1 + sum(count_nodes(n, i + 1) for i in range(start, n))
print(count_nodes(5))Permutations: order matters
A running order uses every track, and position matters. You can't use a
start index here, because a later track can come first. Keep a used flag
for each track instead:
The tree now has n! leaves: 6 for three tracks and 3,628,800 for ten. Un-choose has to undo everything choose did:
def orders(tracks):
out, path, used = [], [], [False] * len(tracks)
def explore():
if len(path) == len(tracks):
out.append(path[:])
return
for i, track in enumerate(tracks):
if not used[i]:
used[i] = True
path.append(track)
explore()
path.pop() # forgot: used[i] = False
explore()
return out
print(len(orders(["a", "b", "c"])))Combination sums: the mix finder
Now the task's shape. Pick tracks, each at most once, whose lengths add up to
exactly the slot. It's the subsets template with a running total, recording
only when the total hits the slot:
Look at the order. The search always tries earlier tracks first, so mixes come
out sorted by the positions of their tracks: (0, 1), then (0, 2, 4),
then (2, 3). That's exactly the order the task asks for.
Pruning: cut dead branches early
That continue is pruning. It never steps into a branch that can't lead to
an answer. Count the calls with and without it:
If the lengths are sorted, you can prune harder. Once one track overflows,
every later one does too, so break instead of continue. On unsorted input
that same break is a bug:
def count_mixes(lengths, slot, start=0, total=0):
if total == slot:
return 1
found = 0
for i in range(start, len(lengths)):
if total + lengths[i] > slot:
break # "nothing after this can fit either"
found += count_mixes(lengths, slot, i + 1, total + lengths[i])
return found
print(count_mixes([5, 9, 2], 7))The task keeps tracks in input order, so it uses continue. It's the right call
whenever sorting would change the answer's order.
| Problem | Nodes in the tree | Time | Extra space |
|---|---|---|---|
| Subsets | 2ⁿ | O(n · 2ⁿ) | O(n) depth, plus output |
| Permutations | about e · n! | O(n · n!) | O(n) |
| Combination sum, each track once | at most 2ⁿ | O(n · 2ⁿ) worst case | O(n) |
| ...with pruning | far fewer in practice | same worst case | O(n) |
❓ Cross-question: "Why not
itertools.combinations?" For a dozen tracks, it's fine. But it builds all 2ⁿ candidates and filters afterwards, so it can't prune. It also yields answers grouped by size, not in position order.
Coming from Java/JS:
path[:]isnew ArrayList<>(path)/[...path]. The nestedexplorecloses overoutandpathlike a JS closure. In Java you'd pass them as parameters.
Idioms & real-world patterns
yield answers instead of collecting them
A generator hands out each answer as it's found, so the caller can stop early.
Passing an immutable tuple (path + (x,)) gives every call its own path, so
there's nothing to un-choose, at the cost of a copy per step:
⚡ Advanced: duplicate lengths without duplicate mixes
With lengths [1, 1, 2] and slot 3, the plain search finds [1, 2] twice, once
for each 1. Sort the lengths, then skip a value that equals the one just
before it at the same level of the tree:
🎯 Your turn
Write exact_mixes(tracks, slot). Each track is [name, minutes], with minutes a
positive whole number. Return every combination of tracks, each track used at
most once, whose minutes add up to exactly slot. Each mix is a list of names.
- Each mix keeps its tracks in input order.
- Mixes are ordered by the positions of their tracks: compare first positions, then second, and so on. That's the order the choose/explore/un-choose search finds them in.
exact_mixes([["Aurora", 4], ["Blink", 3], ["Cobalt", 2], ["Drift", 5], ["Echo", 1]], 7)
→ [["Aurora", "Blink"], ["Aurora", "Cobalt", "Echo"], ["Cobalt", "Drift"]]
Hint: explore(start, total) with path holding chosen positions. When
total == slot, record their names. continue past any track that would overflow.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅