Introduction to Backtracking

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning ("backtracking" from) those that fail to satisfy the constraints. Think of it as exploring a tree of decisions, where each branch represents a choice.

The Core Idea

Backtracking follows a simple pattern:

1. Choose: Make a decision from available options
2. Explore: Recursively explore with that decision
3. Unchoose: Undo the decision (backtrack) and try the next option

def backtrack(candidate):
    if is_solution(candidate):
        output(candidate)
        return

    for choice in available_choices(candidate):
        make_choice(candidate, choice)
        backtrack(candidate)
        undo_choice(candidate, choice)  # Backtrack

Visualizing as a Decision Tree

Problem: Generate all subsets of [1, 2]

                     []
                   /    \
            include 1    exclude 1
                /            \
              [1]            []
             /   \          /   \
       inc 2   exc 2   inc 2   exc 2
         /        \      /        \
      [1,2]      [1]    [2]       []

Subsets: [], [1], [2], [1, 2]

Each path from root to leaf represents one complete solution.

Template

def backtrack(path, choices):
    # Base case: found a solution
    if is_complete(path):
        result.append(path.copy())
        return

    for choice in choices:
        if is_valid(choice, path):
            # Make choice
            path.append(choice)

            # Recurse
            backtrack(path, remaining_choices)

            # Undo choice (backtrack)
            path.pop()

Example: Generate All Subsets

Given [1, 2, 3], generate all subsets.

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path.copy())

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

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

Decision tree for [1, 2, 3]:

start=0, path=[]
├── i=0: path=[1]
│   ├── i=1: path=[1,2]
│   │   └── i=2: path=[1,2,3] → add, backtrack to [1,2]
│   │   └── backtrack to [1]
│   └── i=2: path=[1,3] → add, backtrack to [1]
│   └── backtrack to []
├── i=1: path=[2]
│   └── i=2: path=[2,3] → add, backtrack to [2]
│   └── backtrack to []
└── i=2: path=[3] → add, backtrack to []

Example: Generate Permutations

Given [1, 2, 3], generate all permutations.

def permutations(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path.copy())
            return

        for i in range(len(remaining)):
            # Choose
            path.append(remaining[i])

            # Explore with remaining elements
            backtrack(path, remaining[:i] + remaining[i+1:])

            # Unchoose
            path.pop()

    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]]

Alternative using a "used" array:

def permutations_used(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path.copy())
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack(path)

            path.pop()
            used[i] = False

    backtrack([])
    return result

Example: Combinations

Choose k elements from n elements.

def combinations(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path.copy())
            return

        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combinations(4, 2))
# [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Pruning: Early Termination

Pruning eliminates branches that can't lead to valid solutions:

def combinations_with_pruning(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path.copy())
            return

        # Pruning: not enough elements left
        remaining_needed = k - len(path)
        if n - start + 1 < remaining_needed:
            return

        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

Example: N-Queens

Place n queens on an n×n chessboard so no two attack each other.

def solve_n_queens(n):
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]

    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False

        # Check upper left diagonal
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1

        # Check upper right diagonal
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1

        return True

    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return

        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'

    backtrack(0)
    return result

Backtracking vs Other Approaches

| Approach | Description | Use Case | |----------|-------------|----------| | Backtracking | Try all possibilities with pruning | Constraint satisfaction | | Dynamic Programming | Cache subproblem solutions | Overlapping subproblems | | Greedy | Make locally optimal choices | Optimization (when works) | | BFS/DFS | Graph/tree traversal | Finding paths |

Common Patterns

1. Subset/Combination Pattern

for i in range(start, len(nums)):
    path.append(nums[i])
    backtrack(i + 1, path)  # i + 1 to avoid reuse
    path.pop()

2. Permutation Pattern

for i in range(len(nums)):
    if used[i]:
        continue
    used[i] = True
    path.append(nums[i])
    backtrack(path)
    path.pop()
    used[i] = False

3. Constraint Checking Pattern

if is_valid(choice, path):
    path.append(choice)
    backtrack(path)
    path.pop()

Time Complexity

| Problem | Time Complexity | |---------|-----------------| | Subsets | O(2^n) | | Permutations | O(n!) | | Combinations | O(C(n,k)) | | N-Queens | O(n!) |

Key Takeaways

1. Backtracking = Choose → Explore → Unchoose
2. Visualize as exploring a decision tree
3. Add solution when complete, backtrack when done
4. Use pruning to skip invalid branches early
5. Remember to copy the path when storing solutions
6. Common for permutations, combinations, constraint satisfaction

Backtracking is a powerful technique for exhaustive search with constraints. The key is understanding the decision tree and implementing the choose/explore/unchoose pattern correctly. Pruning makes it practical for larger inputs.