Advanced

Patterns & Tips

This lesson consolidates everything into copy-paste-ready templates, a decision framework for choosing the right backtracking variant, and answers to frequently asked questions.

Template 1: Permutations

Use when order matters and every element must be used exactly once.

def permutation_template(nums):
    """Permutation template: use visited set, iterate from 0.

    - Result collected when path length equals input length
    - For unique permutations: sort + skip duplicates
    """
    result = []

    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if i in used:
                continue
            # For unique: if i > 0 and nums[i] == nums[i-1]
            #             and (i-1) not in used: continue
            used.add(i)
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used.remove(i)

    backtrack([], set())
    return result

Template 2: Combinations

Use when order does not matter and you pick k elements from n.

def combination_template(n, k):
    """Combination template: use start index, no revisiting.

    - Result collected when path length equals k
    - Upper bound pruning: i can go at most to n - (k - len(path)) + 1
    """
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n - (k - len(path)) + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

Template 3: Subsets

Use when you need all possible subsets (power set).

def subset_template(nums):
    """Subset template: collect at every node, not just leaves.

    - Result added at every recursion level
    - For unique: sort + skip duplicates at same level
    """
    result = []

    def backtrack(start, path):
        result.append(path[:])  # collect at every node
        for i in range(start, len(nums)):
            # For unique: if i > start and nums[i] == nums[i-1]: continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

Template 4: Grid/Matrix Backtracking

Use for path finding, word search, and constraint satisfaction on 2D grids.

def grid_backtrack_template(grid, start_r, start_c):
    """Grid backtracking template: in-place marking.

    - Mark current cell visited (modify grid or use set)
    - Explore all valid neighbors
    - Unmark on backtrack
    """
    rows, cols = len(grid), len(grid[0])

    def backtrack(r, c, state):
        # Base case: check if goal reached
        if is_goal(r, c, state):
            record_solution(state)
            return

        # Mark visited
        original = grid[r][c]
        grid[r][c] = '#'  # or add to visited set

        # Explore neighbors
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and
                    grid[nr][nc] != '#' and is_valid(nr, nc, state)):
                backtrack(nr, nc, updated_state)

        # Unmark (backtrack)
        grid[r][c] = original

    backtrack(start_r, start_c, initial_state)

Template 5: String Partitioning

Use for palindrome partitioning, word break, IP address restoration.

def string_partition_template(s):
    """String partition template: try all prefix lengths.

    - At each position, try segments of length 1, 2, 3, ...
    - Validate segment before recursing
    - Recurse on remaining string
    """
    result = []

    def backtrack(start, parts):
        if start == len(s):
            result.append(parts[:])
            return

        for end in range(start + 1, len(s) + 1):
            segment = s[start:end]
            if is_valid_segment(segment):
                parts.append(segment)
                backtrack(end, parts)
                parts.pop()

    backtrack(0, [])
    return result

Template 6: Constraint Satisfaction (CSP)

Use for Sudoku, N-Queens, and scheduling problems.

def csp_template(variables, domains, constraints):
    """CSP template: assign values to variables under constraints.

    - Find next unassigned variable
    - Try each value in its domain
    - Check constraints before assigning
    - Backtrack if no valid value found
    """
    def backtrack(assignment):
        if len(assignment) == len(variables):
            return assignment.copy()  # solution found

        var = select_unassigned(variables, assignment)

        for value in domains[var]:
            if is_consistent(var, value, assignment, constraints):
                assignment[var] = value
                result = backtrack(assignment)
                if result is not None:
                    return result
                del assignment[var]

        return None  # no valid assignment

    return backtrack({})

Decision Framework: Which Template to Use?

Common Mistakes to Avoid

Mistake	Fix
Forgetting to copy the path before appending to result	Always use result.append(path[:]) not result.append(path)
Not backtracking (forgetting path.pop())	Every append must have a matching pop
Using continue instead of break for sorted pruning	break prunes the entire remaining subtree; continue only skips one element
Wrong start index for combinations vs permutations	Combinations: start = i + 1. Permutations: always start from 0 with visited set
Modifying the input without restoring it	Always restore the original value after backtracking (grid problems)
Stack overflow on deep recursion in Python	Use sys.setrecursionlimit() or convert to iterative with explicit stack
Not handling empty input	Add if not nums: return [[]] or return [] depending on the problem
Duplicate results with duplicate inputs	Sort the input, then skip if i > start and nums[i] == nums[i-1]

Interview Execution Tips

Frequently Asked Questions

Complete Problem Index

#	Problem	Pattern	Difficulty	Lesson
1	Permutations (LC 46)	Permutation	Medium	Lesson 2
2	Permutations II (LC 47)	Permutation + Dedup	Medium	Lesson 2
3	Combinations (LC 77)	Combination	Medium	Lesson 2
4	Combination Sum (LC 39)	Combination + Reuse	Medium	Lesson 2
5	Letter Case Permutation (LC 784)	Binary Branch	Medium	Lesson 2
6	Subsets (LC 78)	Subset	Medium	Lesson 3
7	Subsets II (LC 90)	Subset + Dedup	Medium	Lesson 3
8	Combination Sum II (LC 40)	Subset + Sum + Dedup	Medium	Lesson 3
9	Subset Sum (LC 494 variant)	Subset + Memo	Medium	Lesson 3
10	Partition K Equal Subsets (LC 698)	Partition + Symmetry	Hard	Lesson 3
11	Word Search (LC 79)	Grid Backtrack	Medium	Lesson 4
12	N-Queens (LC 51)	CSP	Hard	Lesson 4
13	Sudoku Solver (LC 37)	CSP	Hard	Lesson 4
14	Rat in a Maze	Grid Path	Medium	Lesson 4
15	Unique Paths with Obstacles (LC 63)	Grid + Memo	Medium	Lesson 4
16	Palindrome Partitioning (LC 131)	String Partition	Medium	Lesson 5
17	Generate Parentheses (LC 22)	Constrained Generation	Medium	Lesson 5
18	Letter Combinations (LC 17)	Mapping + Backtrack	Medium	Lesson 5
19	Restore IP Addresses (LC 93)	String Partition	Medium	Lesson 5
20	Word Break II (LC 140)	Partition + Memo	Hard	Lesson 5