DSA Backtracking

Backtracking solves a problem by building an answer one choice at a time. When a choice leads to a dead end, the program undoes that choice and tries a different one. The method explores possibilities in an organized way and drops bad paths early.

Picture a walker inside a maze. At every fork, the walker picks a path. When the path ends at a wall, the walker returns to the last fork and tries another route. Walking back is the "backtrack" in the name.

The Three Steps

• Choose: pick one option from the available choices.
• Explore: move forward with that option using a recursive call.
• Undo: remove the option so the next choice starts fresh.

Backtracking relies on recursion, so review the recursion topic if the call stack feels unfamiliar.

Decision Tree Diagram

Every backtracking problem forms a tree of decisions. The program walks the tree depth first.

Choose letters from [A, B]

                 start
               /       \
          pick A       skip A
          /    \       /     \
      pick B  skip B pick B  skip B
      [A,B]   [A]    [B]     []

The four leaves show every possible group of letters. Each leaf is one finished answer.

Example: Generate All Subsets

A subset is any group of items taken from a list, including the empty group. A list of 3 items has 8 subsets.

def subsets(items):
    result = []
    current = []

    def explore(index):
        if index == len(items):
            result.append(current[:])
            return
        current.append(items[index])    # choose
        explore(index + 1)              # explore
        current.pop()                   # undo
        explore(index + 1)              # explore without the item

    explore(0)
    return result

print(subsets([1, 2, 3]))

The output lists [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], and []. The line current[:] copies the list, which protects each saved answer from later changes.

Example: Generate All Permutations

A permutation is one ordering of all items. The word "CAT" has 6 orderings.

def permutations(items):
    result = []
    used = [False] * len(items)
    current = []

    def explore():
        if len(current) == len(items):
            result.append(current[:])
            return
        for i in range(len(items)):
            if used[i]:
                continue
            used[i] = True
            current.append(items[i])
            explore()
            current.pop()
            used[i] = False

    explore()
    return result

print(permutations(["C", "A", "T"]))

Start with []
 pick C -> [C]
   pick A -> [C, A]
     pick T -> [C, A, T]  (answer)
   pick T -> [C, T]
     pick A -> [C, T, A]  (answer)
 pick A -> [A]
   ...and so on for A and T as the first letter

Pruning: Skipping Bad Paths

Pruning stops a path as soon as it cannot lead to a valid answer. A pruned branch saves a huge amount of work.

Example: Combinations That Reach a Sum

Find groups of numbers from [2, 3, 5] that add up to 8. Numbers may repeat.

def combo_sum(numbers, target):
    result = []

    def explore(start, current, total):
        if total == target:
            result.append(current[:])
            return
        if total > target:
            return                       # prune
        for i in range(start, len(numbers)):
            current.append(numbers[i])
            explore(i, current, total + numbers[i])
            current.pop()

    explore(0, [], 0)
    return result

print(combo_sum([2, 3, 5], 8))   # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

The check total > target ends any branch that already overshoots.

Famous Backtracking Problems

• N-Queens places queens on a chessboard so none attack each other.
• Sudoku solvers fill empty cells and undo wrong guesses.
• Word search finds a word inside a grid of letters.
• Maze solvers find a path from the entrance to the exit.

Complexity

Backtracking can grow very fast. Subsets take O(2^n) time and permutations take O(n!) time. Pruning lowers the real cost, but the worst case stays large. Use the technique on small inputs or on problems with strong pruning rules.

Common Mistakes

Forgetting the undo step ranks as the most common error. Without it, old choices leak into later paths and the answers come out wrong. Saving the live list without copying it causes a similar problem, since later changes alter earlier results. Always store a copy, such as current[:], when you record an answer. Print the list after each choose and undo step on a tiny input to see the exact flow.

Key Points

• Backtracking builds answers step by step and undoes failed steps.
• The pattern is choose, explore, undo.
• Recursion drives the exploration of the decision tree.
• Pruning cuts branches that cannot succeed.
• Subsets, permutations, Sudoku, and N-Queens all use this method.