Backtracking

Explore every possibility, but smartly prune dead ends

Picture yourself lost in a maze. You walk down a path. It ends in a wall. So you go back to the last fork and try a different path. Wall again? Back up, try the next. You keep doing this until one path leads out.
That is backtracking, and you have done it your whole life. In code it is the same simple loop: make a choice, see if it can work, and if it cannot, undo it and try the next choice. Step through one below.

The undo is the whole trick, and it is what the name means: when a path fails, you *back* up and *track* to the next option, instead of starting the whole maze over.
Two things make it fast enough to be useful:

You build the answer one small step at a time. Choose, then choose again, only going deeper while things still look possible.

You give up early. The moment a half-built answer clearly cannot work, you drop it and back up, skipping the millions of full answers that would have started that way. That early giving-up is called pruning, and it is why a Sudoku solver can try billions of arrangements without ever finishing most of them.

This same try-fail-undo loop solves mazes, Sudoku, seating puzzles, word games, and "list every possible combination" questions. Learn to see the maze and you have seen them all.

Generate all permutationspython

def permutations(nums):
    result = []

    def backtrack(current, remaining):
        if not remaining:           # Base case: used all numbers
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])              # Choose
            backtrack(current, remaining[:i] + remaining[i+1:])  # Explore
            current.pop()                             # Unchoose (backtrack)

    backtrack([], nums)
    return result

print(permutations([1, 2, 3]))
# → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

🎯In the Real World...

Sudoku solvers use backtracking: try placing a number, recurse to the next empty cell, and if you get stuck, backtrack and try a different number. The search space is huge but pruning makes it practical.

🤔Quick Check

What does "backtracking" mean in the context of the algorithm?

🎯

Phase Complete!

Recursion

Recursion and backtracking unlocked. These are the backbone of tree algorithms, graph search, and dynamic programming. Hash maps are next.

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Subsets

Generate all possible subsets (power set) of a list of unique numbers.
Expected output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next