Generate choices with backtracking
Build candidates step by step and undo choices to explore every option.
- Structure a backtracking search: choose, explore, un-choose.
- Generate subsets, combinations, and permutations.
- Prune branches that cannot lead to a solution.
Backtracking explores every candidate solution by building it one choice at a time. At each step you choose an option, explore further recursively, then un-choose it to try the next option. It solves “generate all” problems - subsets, combinations, permutations, valid parentheses - and constraint puzzles like N-Queens and Sudoku.
The backtracking template
1def backtrack(path, choices):
2 if path is complete: record a copy of path; return
3 for choice in choices:
4 if choice is invalid: continue # pruning
5 path.append(choice) # choose
6 backtrack(path, remaining) # explore
7 path.pop() # un-chooseThe output size drives the complexity: there are 2ⁿ subsets and n! permutations, so these algorithms are exponential by nature. Pruning - skipping choices that cannot work - is what keeps them practical.
1def subsets(nums):
2 result = []
3 path = []
4
5 def backtrack(start):
6 result.append(path[:]) # record a copy
7 for i in range(start, len(nums)):
8 path.append(nums[i])
9 backtrack(i + 1)
10 path.pop()
11
12 backtrack(0)
13 return result
14
15print(subsets([1, 2, 3]))[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Passing start forward means each element is only chosen after the ones before it, so [1, 2] and [2, 1] are not both generated. Permutations drop that rule and instead track which elements are already used. Recording path[:] (a copy) matters: appending path itself would store the same list object, which ends up empty.
Key takeaways
Choose, explore, un-choose.
Record copies of the path, not the path itself.
Exponential output means exponential time; prune early.
Lesson quiz
5 questions · pass with 4 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: solve interview problems
Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.
Generate combinations
Read n and k. Print every combination of k numbers chosen from 1..n, one per line with numbers separated by spaces, in lexicographic order. Use backtracking.
- Choose 2 of 4
- Choose 3 of 3
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…