Backtracking

Explore every possibility, but smartly prune dead ends

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning ("backtracking" from) any path that can't lead to a valid solution.
Think of it as a depth-first search through a decision tree, at each node you make a choice, and if it fails, you undo it and try the next option.

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