Find Combinations with Python Backtracking and Pruning
Generate unique positive-integer combinations that sum to a target while pruning impossible branches.
Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons
Video lesson: Find Combinations with Python Backtracking and Pruning
The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube
Jump to a chapter
Read the video transcript
Select a timestamp to watch that moment on YouTube.
- 00:00
Which combinations of two, three, five, and seven add up to ten if each number may be used at most once? We can find two plus three plus five, and three plus seven. A brute-force search can enumerate decisions: include a number, continue with later numbers, and undo that inclusion before trying a sibling branch. That is backtracking. The main challenge is not typing a recursive call. It is keeping each branch's state correct while the same path list is reused. We will deliberately run a broken version whose output looks bizarre, diagnose the mutable reference, and then add a pruning rule that is justified by sorted positive input.
- 00:41
Backtracking searches a decision tree by choosing a value, exploring the rest of the branch, then undoing that choice. This lesson uses distinct positive integers and a target sum. Each value may appear at most once in a combination. Sort the candidates and pass a start index so later recursion only considers later values; this prevents different orders of the same combination. A path list records the current choices. At the target, save a snapshot of the path rather than the mutable path object. Backtracking is useful when you need all valid answers, not just one pair. The broken search reaches valid totals but appends its path list directly to results.
- 01:24
It prints empty lists at the end. Why did the answers vanish? At the moment of discovery, path contains the chosen numbers. The recursive function then returns to its parent and pops the most recent choice. Every saved result points to that exact same list object. By the time all branches finish, the shared path has been popped back to empty. This is not a problem with addition or the base case. It is a problem with the lifetime of a mutable object. If we only tested the number of results, the bug could survive; inspect the contents as well. The broken version appends the path list itself to results.
- 02:05
After recursion returns, it pops values from that same list, so every saved reference eventually points to the final empty path. The program may print a list of empty lists even though the search visited valid sums. Inspect object identity and the path at the moment an answer is found. This illustrates a general Python issue: storing a mutable object stores a reference, not a frozen historical value. The right fix is to append tuple(path) or path.copy() when the target is reached. The diagnostic run checks whether the saved result and the active path are the same object. The answer is true.
- 02:45
We then pop all values and observe that the saved result changes too. A copy at the moment of a complete answer fixes this. We will choose tuple(path), because a completed combination should not be mutated later. We also need a rule to avoid saving the same combination in multiple orders. The recursive function receives a start index and considers only candidates at or after it. After choosing index i, the next call begins at i plus one. This both prevents reuse of one candidate position and avoids permutation duplicates such as two, three, five versus five, three, two.
- 03:25
All candidates are positive and sorted. If the next candidate exceeds the remaining target, every later candidate also exceeds it, so break out of the loop. This is safe pruning based on a stated invariant; it would fail with negative values or an unsorted list. Passing index plus one to the recursive call prevents reuse of the same candidate. After the call, pop the appended value so the parent branch resumes with the path it had before that choice. Save tuples and sort final results for a stable order. This gives a small, inspectable implementation without a global mutable results variable.
- 04:05
Now run the corrected search. We sort the distinct positive candidates. On each branch, if a candidate is larger than the remaining sum, we break because every later sorted candidate is at least as large. That is pruning: skipping branches proven unable to succeed. It would be unsafe with negative values, where a later negative number might compensate, so this function rejects nonpositive candidates. It also rejects duplicate candidate values to keep the contract simple. At remaining zero, tuple(path) is saved. After every recursive call, the matching pop restores the path for the next choice.
- 04:45
The output now contains the two expected tuples, in stable sorted order. Follow one successful branch all the way down: choose two, then three, then five. The remaining total is zero, so tuple(path) captures (2, 3, 5). Control returns to the previous frame, which pops five. That pop changes the working path but cannot change the saved tuple. The same process repeats across sibling branches. Because each recursive call starts after its chosen index, one candidate cannot be selected twice and a combination is visited in one order. The break rule is valid only because candidates are positive and sorted.
- 05:27
In general, pruning should be treated like a proof obligation: state why every skipped branch is impossible before discarding it. The final run checks a target with no solution, a zero target with an empty combination, and duplicate input rejection. Notice that returning all combinations can still require enormous work for larger inputs, even with pruning. The tree may have exponentially many branches or even exponentially many answers. Do not promise that backtracking becomes fast just because it prunes some branches. Use it when the input is bounded and when enumeration is genuinely needed. As you complete the task on the lesson page, say out loud what each line
- 06:10
contributes: start index for uniqueness, append for choice, recursive call for exploration, pop for undo, tuple for a stable answer, and sorted positivity for safe pruning. For candidates [2, 3, 5, 7] and target 10, the answers are (2, 3, 5) and (3, 7). The verification run checks no solution and an invalid duplicate candidate. Reject nonpositive values and duplicate candidates because the algorithm's uniqueness and pruning assumptions are tailored to distinct positive integers. Backtracking can still take exponential time in the worst case: pruning reduces explored branches but does not change that general risk.
- 06:54
Use it when the search space is appropriately bounded and when complete enumeration is actually needed.
Understand the concept
Backtracking searches a decision tree by choosing a value, exploring the rest of the branch, then undoing that choice. This lesson uses distinct positive integers and a target sum. Each value may appear at most once in a combination. Sort the candidates and pass a start index so later recursion only considers later values; this prevents different orders of the same combination. A path list records the current choices. At the target, save a snapshot of the path rather than the mutable path object. Backtracking is useful when you need all valid answers, not just one pair.
The broken version appends the path list itself to results. After recursion returns, it pops values from that same list, so every saved reference eventually points to the final empty path. The program may print a list of empty lists even though the search visited valid sums. Inspect object identity and the path at the moment an answer is found. This illustrates a general Python issue: storing a mutable object stores a reference, not a frozen historical value. The right fix is to append tuple(path) or path.copy() when the target is reached.
All candidates are positive and sorted. If the next candidate exceeds the remaining target, every later candidate also exceeds it, so break out of the loop. This is safe pruning based on a stated invariant; it would fail with negative values or an unsorted list. Passing index plus one to the recursive call prevents reuse of the same candidate. After the call, pop the appended value so the parent branch resumes with the path it had before that choice. Save tuples and sort final results for a stable order. This gives a small, inspectable implementation without a global mutable results variable.
For candidates [2, 3, 5, 7] and target 10, the answers are (2, 3, 5) and (3, 7). The verification run checks no solution and an invalid duplicate candidate. Reject nonpositive values and duplicate candidates because the algorithm's uniqueness and pruning assumptions are tailored to distinct positive integers. Backtracking can still take exponential time in the worst case: pruning reduces explored branches but does not change that general risk. Use it when the search space is appropriately bounded and when complete enumeration is actually needed.
- Choose, explore, and undo
- Snapshot a mutable path
- Advance start index to avoid permutations
- Prune only under a proven ordering invariant
See it step by step
Read the code, predict the output, then compare it with the result.
01. Observe a changing reference
path = [2,3,5]; results = []
results.append(path)
path.pop()
print(results)
[[2, 3]]The saved list points to the same object and changes when the path changes.
02. Capture an immutable answer
path = [2,3,5]; results = []
results.append(tuple(path))
path.pop()
print(results)
[(2, 3, 5)]The tuple preserves the combination that existed before the pop.
03. Prune sorted positive values
values = sorted([7,2,5,3]); remaining = 4
for value in values:
if value > remaining: break
print('candidate', value)
candidate 2
candidate 3After the first value above four, every later value is also too large.
A closer look
Follow the reasoning, inspect each result, then try the suggested changes in the console below.
Identify shared path state
Backtracking searches a decision tree by choosing a value, exploring the rest of the branch, then undoing that choice. This lesson uses distinct positive integers and a target sum. Each value may appear at most once in a combination. Sort the candidates and pass a start index so later recursion only considers later values; this prevents different orders of the same combination. A path list records the current choices. At the target, save a snapshot of the path rather than the mutable path object. Backtracking is useful when you need all valid answers, not just one pair.
Store a list in results and then mutate the original list. Python does not make a copy merely because the list was appended. Look at the result before and after pop to see why successful recursive paths seem to disappear.
path = [2,3,5]; results = []
results.append(path)
path.pop()
print(results)
[[2, 3]]- Append and pop a shared list.
- Read the changed result.
Snapshot complete combinations
The broken version appends the path list itself to results. After recursion returns, it pops values from that same list, so every saved reference eventually points to the final empty path. The program may print a list of empty lists even though the search visited valid sums. Inspect object identity and the path at the moment an answer is found. This illustrates a general Python issue: storing a mutable object stores a reference, not a frozen historical value. The right fix is to append tuple(path) or path.copy() when the target is reached.
At the target, convert the current path to a tuple. The tuple records the chosen values, while the path remains available for backtracking. The recursive call and pop should form a balanced pair: choose one value, explore, then undo exactly that choice.
path = [2,3,5]; results = []
results.append(tuple(path))
path.pop()
print(results)
[(2, 3, 5)]- Use tuple(path) at the base case.
- Check that results stay intact after pop.
Explain the pruning rule
All candidates are positive and sorted. If the next candidate exceeds the remaining target, every later candidate also exceeds it, so break out of the loop. This is safe pruning based on a stated invariant; it would fail with negative values or an unsorted list. Passing index plus one to the recursive call prevents reuse of the same candidate. After the call, pop the appended value so the parent branch resumes with the path it had before that choice. Save tuples and sort final results for a stable order. This gives a small, inspectable implementation without a global mutable results variable.
Sorting alone is not enough if negative values are allowed. This project's positive-integer contract makes an oversized candidate and all later candidates impossible for the remaining target. Stop the current loop, but let other branches continue exploring.
values = sorted([7,2,5,3]); remaining = 4
for value in values:
if value > remaining: break
print('candidate', value)
candidate 2
candidate 3- Sort candidates and state positivity.
- Break when a value exceeds remaining.
Try it in Python
Edit the example and run it. Python starts in your browser the first time you click Run.
Python console
Ready to runNeed input()? Add one value per line
Your output appears here.
Need a hint?
Sort values, save tuple(path) at remaining == 0, recurse from index+1, and break when a positive candidate exceeds remaining.
Complete the task and select Check task to verify your code.
Quick quiz
Three questions. You can change your answers and try again.
Typical mistakes
Everyone meets these errors. See what causes them and how to fix them.
Saving a shared mutable path
results.append(path)results.append(tuple(path))What happens: Saved combinations turn into empty lists after backtracking.
A tuple snapshots the chosen values at that moment.
Pruning without a precondition
break on any candidate above remaining in unsorted inputsort distinct positive candidates before pruningWhat happens: A smaller later candidate may be skipped.
Only ordered positive candidates support this branch elimination.