Backtracking Patterns — Comprehensive Guide

def backtrack(state, choices):
    if is_complete(state):
        process_solution(state)
        return

    for candidate in choices:
        if is_valid(state, candidate):
            # 1. Choose
            apply(state, candidate)

            # 2. Explore
            backtrack(state, next_choices)

            # 3. Unchoose
            undo(state, candidate)

def solve(n):
    result = []

    def backtrack(path):
        # Base case: solution is complete
        if len(path) == n:
            result.append(path[:])  # copy!
            return

        for candidate in get_candidates(path):
            path.append(candidate)       # choose
            backtrack(path)              # explore
            path.pop()                   # unchoose

    backtrack([])
    return result

# WRONG — all entries point to the same list
result.append(path)

# CORRECT — snapshot the current state
result.append(path[:])
result.append(list(path))
result.append(tuple(path))

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

    def backtrack(path):
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path)
                path.pop()
                used[i] = False

    backtrack([])
    return result

def permutations_swap(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # choose
            backtrack(start + 1)                          # explore
            nums[start], nums[i] = nums[i], nums[start]  # unchoose

    backtrack(0)
    return result

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

    def backtrack(path):
        if len(path) == n:          # leaf: a full permutation
            result.append(path[:])  # copy — path keeps mutating
            return
        for i in range(n):
            if used[i]:             # prune: element already placed
                continue
            used[i] = True          # choose
            path.append(nums[i])
            backtrack(path)         # explore
            path.pop()              # unchoose
            used[i] = False

    backtrack([])
    return result

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

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

        # Pruning: need (k - len(path)) more elements,
        # and only (n - start + 1) are available
        for i in range(start, n + 1):
            if n - i + 1 < k - len(path):  # not enough remaining
                break
            path.append(i)
            backtrack(i + 1, path)  # i+1 to avoid reuse
            path.pop()

    backtrack(1, [])
    return result

def combinations_with_repetition(candidates, k):
    """Choose k elements, each can be used multiple times."""
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path)     # i, NOT i+1 — allow reuse
            path.pop()

    backtrack(0, [])
    return result

def subsets_include_exclude(nums):
    result = []

    def backtrack(index, path):
        if index == len(nums):
            result.append(path[:])
            return

        # Include nums[index]
        path.append(nums[index])
        backtrack(index + 1, path)
        path.pop()

        # Exclude nums[index]
        backtrack(index + 1, path)

    backtrack(0, [])
    return result

def subsets_iterative_growth(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # every partial path is a valid subset

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

    backtrack(0, [])
    return result

def subsets_bitmask(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)
    return result

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])          # record EVERY node, not just leaves
        for i in range(start, len(nums)):
            path.append(nums[i])        # choose nums[i]
            backtrack(i + 1, path)      # explore; i+1 = never look back
            path.pop()                  # unchoose

    backtrack(0, [])
    return result

def subsets_with_dup(nums):
    nums.sort()  # critical!
    result = []

    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            # Skip duplicates at the same decision level
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

def permutations_with_dup(nums):
    nums.sort()  # critical!
    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
            # Skip duplicate: if nums[i] == nums[i-1] and nums[i-1] was NOT used
            # at this level, then we'd generate the same subtree
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result

def combination_sum_with_dup(candidates, target):
    """Each number used at most once; duplicates in input."""
    candidates.sort()
    result = []

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # pruning: sorted, so all future too big
            if i > start and candidates[i] == candidates[i - 1]:
                continue  # skip duplicate at same level
            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

def subsetsWithDup(nums):
    nums.sort()                          # equal values become adjacent
    result = []

    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                 # skip duplicate SIBLING at this level
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

def solve_n_queens(n):
    result = []
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col

    def backtrack(row, queens):
        if row == n:
            # Build board representation
            board = []
            for r, c in sorted(queens):
                board.append('.' * c + 'Q' + '.' * (n - c - 1))
            result.append(board)
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue

            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            queens.append((row, col))

            backtrack(row + 1, queens)

            queens.pop()
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0, [])
    return result

def solve_sudoku(board):
    """board: 9x9 list of lists, 0 = empty."""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    # Initialize constraint sets
    empty = []
    for r in range(9):
        for c in range(9):
            if board[r][c] != 0:
                val = board[r][c]
                rows[r].add(val)
                cols[c].add(val)
                boxes[(r // 3) * 3 + c // 3].add(val)
            else:
                empty.append((r, c))

    def backtrack(idx):
        if idx == len(empty):
            return True  # all cells filled

        r, c = empty[idx]
        box_id = (r // 3) * 3 + c // 3

        for val in range(1, 10):
            if val in rows[r] or val in cols[c] or val in boxes[box_id]:
                continue

            # Choose
            board[r][c] = val
            rows[r].add(val)
            cols[c].add(val)
            boxes[box_id].add(val)

            # Explore
            if backtrack(idx + 1):
                return True

            # Unchoose
            board[r][c] = 0
            rows[r].remove(val)
            cols[c].remove(val)
            boxes[box_id].remove(val)

        return False  # no valid digit for this cell

    backtrack(0)
    return board

def word_search(board, word):
    R, C = len(board), len(board[0])

    def backtrack(r, c, k):
        if k == len(word):
            return True
        if r < 0 or r >= R or c < 0 or c >= C:
            return False
        if board[r][c] != word[k]:
            return False

        # Mark visited (in-place trick)
        tmp = board[r][c]
        board[r][c] = '#'

        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if backtrack(r + dr, c + dc, k + 1):
                return True

        board[r][c] = tmp  # unchoose
        return False

    for r in range(R):
        for c in range(C):
            if backtrack(r, c, 0):
                return True
    return False

def exist(board, word):
    R, C = len(board), len(board[0])

    def backtrack(r, c, k):
        if k == len(word):                       # matched every char
            return True
        if r < 0 or r >= R or c < 0 or c >= C:   # prune: off-grid
            return False
        if board[r][c] != word[k]:               # prune: wrong char / visited '#'
            return False

        tmp = board[r][c]
        board[r][c] = '#'                        # choose: mark visited
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if backtrack(r + dr, c + dc, k + 1):  # explore neighbors
                return True
        board[r][c] = tmp                        # unchoose: restore
        return False

    return any(backtrack(r, c, 0) for r in range(R) for c in range(C))

def can_partition_k(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k

    nums.sort(reverse=True)  # pruning: try big elements first
    if nums[0] > target:
        return False

    buckets = [0] * k

    def backtrack(index):
        if index == len(nums):
            return all(b == target for b in buckets)

        seen = set()  # avoid putting same value in equivalent empty buckets
        for i in range(k):
            if buckets[i] + nums[index] > target:
                continue
            if buckets[i] in seen:  # symmetry pruning
                continue
            seen.add(buckets[i])

            buckets[i] += nums[index]
            if backtrack(index + 1):
                return True
            buckets[i] -= nums[index]

        return False

    return backtrack(0)

def palindrome_partition(s):
    result = []

    def is_palindrome(l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

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

        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()

    backtrack(0, [])
    return result

def palindrome_partition_optimized(s):
    n = len(s)
    # is_pal[i][j] = True if s[i..j] is palindrome
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n - 1):
        is_pal[i][i + 1] = (s[i] == s[i + 1])
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j] and is_pal[i + 1][j - 1])

    result = []

    def backtrack(start, path):
        if start == n:
            result.append(path[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()

    backtrack(0, [])
    return result

def partition(s):
    result = []

    def is_palindrome(l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

    def backtrack(start, path):
        if start == len(s):              # consumed the whole string
            result.append(path[:])
            return
        for end in range(start, len(s)):        # choose a cut point
            if is_palindrome(start, end):       # prune: non-palindrome prefix
                path.append(s[start:end + 1])   # choose the segment
                backtrack(end + 1, path)        # explore the rest
                path.pop()                      # unchoose

    backtrack(0, [])
    return result

def generate_parentheses(n):
    result = []

    def backtrack(path, open_count, close_count):
        if len(path) == 2 * n:
            result.append(''.join(path))
            return

        if open_count < n:
            path.append('(')
            backtrack(path, open_count + 1, close_count)
            path.pop()

        if close_count < open_count:
            path.append(')')
            backtrack(path, open_count, close_count + 1)
            path.pop()

    backtrack([], 0, 0)
    return result

def generateParenthesis(n):
    result = []

    def backtrack(path, open_count, close_count):
        if len(path) == 2 * n:                # used all n pairs
            result.append(''.join(path))
            return
        if open_count < n:                    # can still open
            path.append('(')
            backtrack(path, open_count + 1, close_count)
            path.pop()
        if close_count < open_count:          # closing stays balanced
            path.append(')')
            backtrack(path, open_count, close_count + 1)
            path.pop()

    backtrack([], 0, 0)
    return result

def letter_combinations(digits):
    if not digits:
        return []

    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    result = []

    def backtrack(index, path):
        if index == len(digits):
            result.append(''.join(path))
            return
        for ch in mapping[digits[index]]:
            path.append(ch)
            backtrack(index + 1, path)
            path.pop()

    backtrack(0, [])
    return result

def restore_ip_addresses(s):
    result = []

    def backtrack(start, parts):
        if len(parts) == 4:
            if start == len(s):
                result.append('.'.join(parts))
            return

        remaining_digits = len(s) - start
        remaining_parts = 4 - len(parts)

        # Pruning: each remaining part needs 1-3 digits
        if remaining_digits < remaining_parts or remaining_digits > remaining_parts * 3:
            return

        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start + length]
            # No leading zeros (except "0" itself)
            if len(segment) > 1 and segment[0] == '0':
                break
            if int(segment) > 255:
                break
            parts.append(segment)
            backtrack(start + length, parts)
            parts.pop()

    backtrack(0, [])
    return result

def add_operators(num, target):
    result = []

    def backtrack(index, path, value, prev_operand):
        if index == len(num):
            if value == target:
                result.append(path)
            return

        for i in range(index, len(num)):
            # No leading zeros
            if i > index and num[index] == '0':
                break

            substr = num[index:i + 1]
            curr = int(substr)

            if index == 0:
                # First number, no operator
                backtrack(i + 1, substr, curr, curr)
            else:
                # Addition
                backtrack(i + 1, path + '+' + substr,
                         value + curr, curr)
                # Subtraction
                backtrack(i + 1, path + '-' + substr,
                         value - curr, -curr)
                # Multiplication (need to undo previous addition/subtraction)
                backtrack(i + 1, path + '*' + substr,
                         value - prev_operand + prev_operand * curr,
                         prev_operand * curr)

    backtrack(0, '', 0, 0)
    return result

# Combination Sum: if remaining < 0, stop
def backtrack(start, path, remaining):
    if remaining < 0:
        return  # PRUNE — overshot the target
    if remaining == 0:
        result.append(path[:])
        return
    ...

# Traveling Salesman: prune if current_cost + estimated_remaining > best_known
def backtrack(current_city, visited, cost):
    lower_bound = cost + estimate_remaining(visited)
    if lower_bound >= best_known:
        return  # PRUNE — can't beat current best

    if len(visited) == n:
        best_known = min(best_known, cost + dist[current_city][0])
        return
    ...

# N-Queens: the board has vertical symmetry
# Only place first queen in columns 0..n//2, mirror the rest
def backtrack(row, queens):
    if row == 0:
        end = (n + 1) // 2  # only half the columns
    else:
        end = n
    for col in range(end):
        ...

# Partition into k subsets: identical empty buckets are interchangeable
seen = set()
for i in range(k):
    if buckets[i] in seen:
        continue  # this bucket state already tried
    seen.add(buckets[i])
    ...

# Sort in decreasing order: large elements fail faster, pruning more branches
nums.sort(reverse=True)

# Sudoku: pick the cell with fewest candidates (MRV heuristic)
def find_best_cell(board):
    min_options = 10
    best = None
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                options = count_valid_digits(r, c)
                if options < min_options:
                    min_options = options
                    best = (r, c)
    return best

# Word Break: can we segment string into dictionary words?
from functools import lru_cache

@lru_cache(maxsize=None)
def can_break(start):
    if start == len(s):
        return True
    for end in range(start + 1, len(s) + 1):
        if s[start:end] in word_set and can_break(end):
            return True
    return False

def permutations_bitmask(nums):
    n = len(nums)
    result = []

    def backtrack(mask, path):
        if mask == (1 << n) - 1:  # all bits set
            result.append(path[:])
            return
        for i in range(n):
            if mask & (1 << i):  # already used
                continue
            path.append(nums[i])
            backtrack(mask | (1 << i), path)
            path.pop()

    backtrack(0, [])
    return result

from functools import lru_cache

def shortest_hamiltonian_path(dist, n):
    """Find shortest path visiting all n cities."""
    @lru_cache(maxsize=None)
    def dp(mask, last):
        if mask == (1 << n) - 1:
            return 0  # or dist[last][0] for cycle

        best = float('inf')
        for nxt in range(n):
            if mask & (1 << nxt):
                continue
            best = min(best, dist[last][nxt] + dp(mask | (1 << nxt), nxt))
        return best

    return min(dp(1 << i, i) for i in range(n))

def n_queens_bitmask(n):
    count = 0

    def backtrack(row, cols, diag1, diag2):
        nonlocal count
        if row == n:
            count += 1
            return

        # Available positions: bits NOT set in any conflict mask
        available = ((1 << n) - 1) & ~(cols | diag1 | diag2)

        while available:
            # Pick lowest set bit
            pos = available & (-available)
            available &= available - 1

            backtrack(
                row + 1,
                cols | pos,
                (diag1 | pos) << 1,    # shift left: row-col increases
                (diag2 | pos) >> 1     # shift right: row+col decreases
            )

    backtrack(0, 0, 0, 0)
    return count

def graph_coloring(adj, n, m):
    """Can we color graph with m colors? adj = adjacency list."""
    colors = [0] * n  # 0 = uncolored

    def is_safe(node, color):
        for neighbor in adj[node]:
            if colors[neighbor] == color:
                return False
        return True

    def backtrack(node):
        if node == n:
            return True

        for color in range(1, m + 1):
            if is_safe(node, color):
                colors[node] = color
                if backtrack(node + 1):
                    return True
                colors[node] = 0

        return False

    return backtrack(0)

def hamiltonian_path(adj, n):
    """Find a Hamiltonian path if one exists."""
    path = []
    visited = [False] * n

    def backtrack(node):
        path.append(node)
        if len(path) == n:
            return True

        visited[node] = True
        for neighbor in adj[node]:
            if not visited[neighbor]:
                if backtrack(neighbor):
                    return True
        visited[node] = False
        path.pop()
        return False

    for start in range(n):
        if backtrack(start):
            return path
    return None

def solve_cryptarithmetic():
    """Solve SEND + MORE = MONEY."""
    letters = 'SENDMORY'  # 8 unique letters
    leading = {'S', 'M'}  # can't be 0

    def backtrack(idx, assignment, used_digits):
        if idx == len(letters):
            # Check the equation
            s = lambda w: int(''.join(str(assignment[c]) for c in w))
            return s('SEND') + s('MORE') == s('MONEY')

        letter = letters[idx]
        start = 1 if letter in leading else 0

        for digit in range(start, 10):
            if digit in used_digits:
                continue
            assignment[letter] = digit
            used_digits.add(digit)
            if backtrack(idx + 1, assignment, used_digits):
                return True
            del assignment[letter]
            used_digits.discard(digit)

        return False

    assignment = {}
    if backtrack(0, assignment, set()):
        return assignment
    return None

def can_achieve(state):
    if is_solution(state):
        return True  # found one!
    for choice in candidates:
        if is_valid(state, choice):
            apply(state, choice)
            if can_achieve(state):  # propagate True immediately
                return True
            undo(state, choice)
    return False  # exhausted all options

best = float('inf')

def find_optimal(state, cost):
    global best
    if is_complete(state):
        best = min(best, cost)
        return
    if cost + lower_bound(state) >= best:
        return  # PRUNE
    for choice in candidates:
        apply(state, choice)
        find_optimal(state, cost + choice_cost)
        undo(state, choice)

def count_solutions(state):
    if is_complete(state):
        return 1
    total = 0
    for choice in candidates:
        if is_valid(state, choice):
            apply(state, choice)
            total += count_solutions(state)
            undo(state, choice)
    return total