Backtracking

Why this module exists

Backtracking is a systematic way to explore all possible configurations of a problem. It's essential for constraint satisfaction problems, combinatorics, and many interview questions involving "generate all possible X."

This module covers:

1. The backtracking template
2. Generating subsets (power set)
3. Generating permutations
4. Constraint-based pruning (N-Queens)

---

1) What is Backtracking?

Backtracking is recursion with choice and undo. At each step:

1. Make a choice
2. Recursively explore
3. Undo the choice (backtrack)

It's DFS on an implicit decision tree where nodes represent partial solutions.

                    []
           /        |        \
         [1]       [2]       [3]
        /   \       |
     [1,2] [1,3]  [2,3]
       |
    [1,2,3]

---

2) The Backtracking Template

Most backtracking problems follow this pattern:

func backtrack(path []int, choices []int, result *[][]int) {
    // Base case: valid solution found
    if isComplete(path) {
        // Make a copy!
        solution := make([]int, len(path))
        copy(solution, path)
        *result = append(*result, solution)
        return
    }

    for _, choice := range choices {
        if !isValid(choice, path) {
            continue  // Prune invalid branches
        }

        // Make choice
        path = append(path, choice)

        // Explore
        backtrack(path, remainingChoices, result)

        // Undo choice (backtrack)
        path = path[:len(path)-1]
    }
}

def backtrack(path, choices, result):
    # Base case: valid solution found
    if is_complete(path):
        result.append(path[:])  # Copy!
        return

    for choice in choices:
        if not is_valid(choice, path):
            continue  # Prune

        # Make choice
        path.append(choice)

        # Explore
        backtrack(path, remaining_choices, result)

        # Undo choice
        path.pop()

Key insight: The path is modified in-place. You MUST copy it when saving results.

---

3) Subsets (Power Set)

Generate all subsets of a set. For [1,2,3], output: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

Approach: At each position, choose to include or exclude the element.

func subsets(nums []int) [][]int {
    result := [][]int{}
    backtrack(nums, 0, []int{}, &result)
    return result
}

func backtrack(nums []int, start int, path []int, result *[][]int) {
    // Every path is a valid subset
    subset := make([]int, len(path))
    copy(subset, path)
    *result = append(*result, subset)

    // Try adding each remaining element
    for i := start; i < len(nums); i++ {
        path = append(path, nums[i])
        backtrack(nums, i+1, path, result)  // i+1 to avoid duplicates
        path = path[:len(path)-1]
    }
}

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # Every path is valid

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

    backtrack(0, [])
    return result

Complexity: O(n * 2^n) - there are 2^n subsets, each takes O(n) to copy.

---

4) Permutations

Generate all permutations of distinct elements. For [1,2,3]: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

Approach: At each position, choose any unused element.

func permute(nums []int) [][]int {
    result := [][]int{}
    used := make([]bool, len(nums))
    backtrack(nums, []int{}, used, &result)
    return result
}

func backtrack(nums []int, path []int, used []bool, result *[][]int) {
    if len(path) == len(nums) {
        perm := make([]int, len(path))
        copy(perm, path)
        *result = append(*result, perm)
        return
    }

    for i := 0; i < len(nums); i++ {
        if used[i] {
            continue
        }

        used[i] = true
        path = append(path, nums[i])

        backtrack(nums, path, used, result)

        path = path[:len(path)-1]
        used[i] = false
    }
}

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

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            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

Complexity: O(n * n!) - there are n! permutations, each takes O(n) to copy.

---

5) N-Queens

Place n queens on an n x n chessboard so no two attack each other. Queens attack along rows, columns, and diagonals.

Key insight: One queen per row, so we just need to decide which column for each row.

Pruning: Track which columns and diagonals are under attack.

func solveNQueens(n int) [][]string {
    result := [][]string{}
    cols := make([]bool, n)      // columns under attack
    diag1 := make([]bool, 2*n-1) // main diagonals (row-col)
    diag2 := make([]bool, 2*n-1) // anti diagonals (row+col)
    board := make([]int, n)      // board[row] = column of queen

    backtrack(0, n, board, cols, diag1, diag2, &result)
    return result
}

func backtrack(row, n int, board []int, cols, diag1, diag2 []bool, result *[][]string) {
    if row == n {
        *result = append(*result, buildBoard(board, n))
        return
    }

    for col := 0; col < n; col++ {
        d1 := row - col + n - 1  // offset to keep positive
        d2 := row + col

        if cols[col] || diag1[d1] || diag2[d2] {
            continue  // Prune: position under attack
        }

        // Place queen
        board[row] = col
        cols[col], diag1[d1], diag2[d2] = true, true, true

        backtrack(row+1, n, board, cols, diag1, diag2, result)

        // Remove queen
        cols[col], diag1[d1], diag2[d2] = false, false, false
    }
}

func buildBoard(board []int, n int) []string {
    result := make([]string, n)
    for row := 0; row < n; row++ {
        line := make([]byte, n)
        for i := range line {
            line[i] = '.'
        }
        line[board[row]] = 'Q'
        result[row] = string(line)
    }
    return result
}

def solve_n_queens(n):
    result = []
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)  # row - col
    diag2 = [False] * (2 * n - 1)  # row + col
    board = []

    def backtrack(row):
        if row == n:
            result.append(build_board(board, n))
            return

        for col in range(n):
            d1 = row - col + n - 1
            d2 = row + col

            if cols[col] or diag1[d1] or diag2[d2]:
                continue

            board.append(col)
            cols[col] = diag1[d1] = diag2[d2] = True

            backtrack(row + 1)

            board.pop()
            cols[col] = diag1[d1] = diag2[d2] = False

    backtrack(0)
    return result

def build_board(board, n):
    return ['.' * col + 'Q' + '.' * (n - col - 1) for col in board]

Diagonal insight:

• Cells on the same main diagonal have equal row - col
• Cells on the same anti-diagonal have equal row + col

---

6) When to Use Backtracking

Backtracking is appropriate when:

• You need to generate all solutions
• Solutions have a recursive structure (build incrementally)
• You can prune invalid paths early
• The search space is exponential but pruning helps

Common problem types:

• Subsets, permutations, combinations
• Constraint satisfaction (N-Queens, Sudoku)
• Path finding with constraints
• Word search, expression generation

---

7) Subsets vs Permutations

Aspect	Subsets	Permutations
Order matters?	No	Yes
Size	Any (0 to n)	Fixed (n)
Choices	Elements after current	All unused elements
Count	2^n	n!

Subsets: "start" index prevents going backward, avoiding duplicates like [2,1].

Permutations: "used" array tracks which elements are already in the path.

---

8) Handling Duplicates

If input contains duplicates, sort first and skip consecutive duplicates:

// For subsets with duplicates
sort.Ints(nums)
for i := start; i < len(nums); i++ {
    // Skip duplicates at the same level
    if i > start && nums[i] == nums[i-1] {
        continue
    }
    // ... rest of backtracking
}

---

9) Common Mistakes

• Forgetting to copy: result = append(result, path) copies the slice header, not the data
• Wrong index: Using i instead of start+1 or i+1 leads to duplicates or infinite loops
• Not undoing state: Must restore all modified state (path, used array, constraint trackers)
• Pruning too late: Check constraints before recursing, not after

---

10) Complexity Analysis

Problem	Solutions	Time	Space
Subsets	2^n	O(n * 2^n)	O(n) recursion
Permutations	n!	O(n * n!)	O(n)
N-Queens	varies	O(n!) worst	O(n)

---

Outcomes

After this module, you should be able to:

• Apply the backtracking template to generate combinations
• Distinguish between subset and permutation patterns
• Use constraint tracking to prune invalid branches
• Handle duplicates in backtracking problems

---

Practice Set

1. Subsets (Medium) — Basic subset generation with backtracking
2. Permutations (Medium) — Generate all permutations using used array
3. N-Queens (Hard) — Constraint satisfaction with diagonal tracking

Start with Subsets to understand the basic pattern, then Permutations to see how the "used" array differs from the "start" index. N-Queens combines backtracking with constraint-based pruning.