After this lesson, you will be able to: Apply the backtracking pattern to systematically explore choices, and solve classic problems like permutations, combinations, N-Queens, and Sudoku.
Backtracking is brute force done intelligently: try a choice, recurse, and undo it if it leads nowhere. It solves constraint problems where you must explore many combinations but can prune branches that cannot possibly work. It builds directly on recursion.
Backtracking explores a tree of choices. At each step you make a choice, recurse to explore the consequences, then undo the choice (backtrack) so you can try the next option. The power comes from pruning: as soon as a partial solution violates a constraint, you abandon that whole branch instead of exploring it. It is the standard approach for puzzles, permutations, combinations, and constraint satisfaction.
Permutations of a list. Notice the choose / recurse / un-choose shape.
def permutations(nums):result = []def backtrack(current, remaining):if not remaining: # base case: a complete arrangementresult.append(current[:])returnfor i in range(len(remaining)):current.append(remaining[i]) # choosebacktrack(current, remaining[:i] + remaining[i+1:]) # recursecurrent.pop() # un-choose (backtrack)backtrack([], nums)return result# permutations([1,2,3]) -> all 6 orderings.# The template: for each option -> choose, recurse, un-choose.
Pure brute force tries every combination, which is exponential or factorial. Backtracking's edge is pruning: in N-Queens, the moment two queens attack each other you stop exploring that placement; in Sudoku, the moment a digit conflicts you backtrack. Good pruning can turn an impossible search into a fast one. The art is checking constraints as early as possible so you cut dead branches before wasting work on them.
The simplest backtracking problem after permutations.
1. For each element, you have two choices: include it or skip it.
2. Recurse with an index that moves forward so you never reuse earlier elements.
3. At each call, record the current subset (every node is a valid subset, not just the leaves).
4. The choose/un-choose here is appending the element then popping it after recursing.
5. subsets([1,2,3]) should produce 8 subsets including the empty set.
Forgetting to undo the choice (the pop / un-choose step), so state leaks across branches. Appending a reference to a mutable list instead of a copy, so all results end up identical (append current[:] or list(current)). Pruning too late or not at all, making the search exponential when it did not need to be. Missing the base case. Confusing when to record the result (subsets record at every node; permutations record only complete arrangements).
Sign in and purchase access to unlock this lesson.