Backtracking Pattern

Input: nums = [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

def subsets(nums):
    """
    Generate all subsets of nums.

    Time Complexity: O(2^n) - 2^n subsets to generate
    Space Complexity: O(n) - recursion depth
    """
    result = []

    def backtrack(start, current):
        """
        Build subsets starting from index start.

        Args:
            start: Index to start considering elements
            current: Current subset being built
        """
        # Add current subset to result
        result.append(current[:])  # Make a copy

        # Try adding each remaining element
        for i in range(start, len(nums)):
            # Choose: add nums[i] to current subset
            current.append(nums[i])

            # Explore: recursively build subsets
            backtrack(i + 1, current)

            # Unchoose: remove nums[i] (backtrack)
            current.pop()

    backtrack(0, [])
    return result

# Alternative: Iterative approach
def subsets_iterative(nums):
    """Generate subsets iteratively."""
    result = [[]]  # Start with empty subset

    for num in nums:
        # For each existing subset, create new subset with num added
        result += [curr + [num] for curr in result]

    return result

# Test
nums = [1, 2, 3]
print(subsets(nums))
# Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

nums = [1, 2, 3]

backtrack(0, [])
  Add [] to result

  i=0: Choose 1
    backtrack(1, [1])
      Add [1] to result

      i=1: Choose 2
        backtrack(2, [1,2])
          Add [1,2] to result

          i=2: Choose 3
            backtrack(3, [1,2,3])
              Add [1,2,3] to result
              No more elements
            Unchoose 3: [1,2]
        Unchoose 2: [1]

      i=2: Choose 3
        backtrack(3, [1,3])
          Add [1,3] to result
          No more elements
        Unchoose 3: [1]
    Unchoose 1: []

  i=1: Choose 2
    backtrack(2, [2])
      Add [2] to result

      i=2: Choose 3
        backtrack(3, [2,3])
          Add [2,3] to result
          No more elements
        Unchoose 3: [2]
    Unchoose 2: []

  i=2: Choose 3
    backtrack(3, [3])
      Add [3] to result
      No more elements
    Unchoose 3: []

Result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Input: nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

def permute(nums):
    """
    Generate all permutations of nums.

    Time Complexity: O(n! * n) - n! permutations, n to copy each
    Space Complexity: O(n) - recursion depth
    """
    result = []

    def backtrack(current, remaining):
        """
        Build permutations with current built and remaining elements.

        Args:
            current: Current permutation being built
            remaining: Elements not yet used
        """
        # Base case: no remaining elements
        if not remaining:
            result.append(current[:])
            return

        # Try each remaining element
        for i in range(len(remaining)):
            # Choose: add remaining[i] to permutation
            element = remaining[i]
            current.append(element)

            # Explore: recurse with remaining elements
            new_remaining = remaining[:i] + remaining[i+1:]
            backtrack(current, new_remaining)

            # Unchoose: remove element (backtrack)
            current.pop()

    backtrack([], nums)
    return result

# Alternative: Using a used set
def permute_with_set(nums):
    """Generate permutations tracking used elements."""
    result = []
    used = set()

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return

        for num in nums:
            if num not in used:
                # Choose
                used.add(num)
                current.append(num)

                # Explore
                backtrack(current)

                # Unchoose
                current.pop()
                used.remove(num)

    backtrack([])
    return result

# Test
nums = [1, 2, 3]
print(permute(nums))
# Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

nums = [1, 2, 3]

backtrack([], [1,2,3])

  i=0: Choose 1
    backtrack([1], [2,3])

      i=0: Choose 2
        backtrack([1,2], [3])

          i=0: Choose 3
            backtrack([1,2,3], [])
              Add [1,2,3] to result
          Unchoose 3
      Unchoose 2

      i=1: Choose 3
        backtrack([1,3], [2])

          i=0: Choose 2
            backtrack([1,3,2], [])
              Add [1,3,2] to result
          Unchoose 2
      Unchoose 3
    Unchoose 1

  i=1: Choose 2
    backtrack([2], [1,3])
      ... generates [2,1,3] and [2,3,1]
    Unchoose 2

  i=2: Choose 3
    backtrack([3], [1,2])
      ... generates [3,1,2] and [3,2,1]
    Unchoose 3

Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Input: n = 4
Output: [
  [".Q..",
   "...Q",
   "Q...",
   "..Q."],
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."]
]

def solve_n_queens(n):
    """
    Solve N-Queens problem.

    Time Complexity: O(n!) - try n positions in first row, n-1 in second, etc.
    Space Complexity: O(n^2) - board storage
    """
    result = []
    board = [['.'] * n for _ in range(n)]

    # Track attacked positions
    cols = set()
    diagonals = set()  # row - col
    anti_diagonals = set()  # row + col

    def is_safe(row, col):
        """Check if placing queen at (row, col) is safe."""
        return (col not in cols and
                (row - col) not in diagonals and
                (row + col) not in anti_diagonals)

    def backtrack(row):
        """Place queens starting from row."""
        if row == n:
            # All queens placed successfully
            result.append([''.join(row) for row in board])
            return

        # Try placing queen in each column
        for col in range(n):
            if is_safe(row, col):
                # Choose: place queen
                board[row][col] = 'Q'
                cols.add(col)
                diagonals.add(row - col)
                anti_diagonals.add(row + col)

                # Explore: place queens in next rows
                backtrack(row + 1)

                # Unchoose: remove queen (backtrack)
                board[row][col] = '.'
                cols.remove(col)
                diagonals.remove(row - col)
                anti_diagonals.remove(row + col)

    backtrack(0)
    return result

# Test
n = 4
solutions = solve_n_queens(n)
for sol in solutions:
    for row in sol:
        print(row)
    print()
# Output: Two valid 4-queens solutions

n = 4

backtrack(row=0)
  Try col=0: Safe? Yes
    Place Q at (0,0)
    cols={0}, diag={0}, anti={0}

    backtrack(row=1)
      Try col=0: Safe? No (col 0 taken)
      Try col=1: Safe? No (diagonal)
      Try col=2: Safe? Yes
        Place Q at (1,2)
        cols={0,2}, diag={0,-1}, anti={0,3}

        backtrack(row=2)
          Try col=0: Safe? No (anti-diagonal)
          Try col=1: Safe? No (diagonal)
          Try col=2: Safe? No (col taken)
          Try col=3: Safe? No (anti-diagonal)
          No valid placement, backtrack

        Remove Q from (1,2)

      Try col=3: Safe? Yes
        Place Q at (1,3)
        ... continue exploring
        Eventually finds solution [.Q.., ...Q, Q..., ..Q.]

  Try col=1: Safe? Yes
    Place Q at (0,1)
    ... explore and find solution [..Q., Q..., ...Q, .Q..]

Result: Two valid solutions

def backtrack_template(problem_input):
    """General backtracking template."""
    result = []

    def backtrack(state, choices):
        """
        Args:
            state: Current solution being built
            choices: Available choices at this step
        """
        # Base case: solution complete
        if is_solution_complete(state):
            result.append(copy_solution(state))
            return

        # Try each choice
        for choice in choices:
            # Prune: skip invalid choices
            if not is_valid(choice, state):
                continue

            # Choose: add choice to state
            make_choice(state, choice)

            # Explore: recurse with updated state
            backtrack(state, get_remaining_choices(choices, choice))

            # Unchoose: remove choice (backtrack)
            undo_choice(state, choice)

    backtrack(initial_state, all_choices)
    return result

# Example: N-Queens
state = {
    'board': [['.'] * n for _ in range(n)],
    'cols': set(),        # Columns under attack
    'diagonals': set(),   # Diagonals under attack
    'anti_diagonals': set()
}

# Example: Permutations
state = {
    'current': [],  # Current permutation being built
    'used': set()   # Elements already used
}

# Keep state minimal - only what's needed for decision making

def get_choices(state):
    """
    Return valid choices at current state.

    For N-Queens: which columns in current row
    For Permutations: which unused elements
    For Sudoku: which numbers (1-9) in current cell
    """
    # This varies by problem
    pass

# Key: Choices should be mutually exclusive
# Each choice leads to different branch of solution tree

def is_valid(choice, state):
    """
    Check if choice satisfies all constraints.

    This is your pruning function - crucial for performance.
    """
    # Example: N-Queens
    # Invalid if: column, diagonal, or anti-diagonal under attack

    # Example: Sudoku
    # Invalid if: number already in row, column, or 3x3 box

    # Return False as early as possible to prune tree
    pass

def backtrack(state, result):
    """
    Universal backtracking template.

    Adapt by:
    1. Changing base case check
    2. Customizing choice generation
    3. Defining what makes choice valid
    4. Specifying how to make/unmake choice
    """
    # BASE CASE: Solution complete
    if is_solution_complete(state):
        result.append(copy_solution(state))
        return

    # RECURSIVE CASE: Try each choice
    for choice in get_choices(state):
        # PRUNE: Skip invalid choices
        if not is_valid(choice, state):
            continue

        # CHOOSE: Make the choice
        make_choice(state, choice)

        # EXPLORE: Recursively solve subproblem
        backtrack(state, result)

        # UNCHOOSE: Undo the choice (backtrack)
        unmake_choice(state, choice)

# Example: Combination Sum
def combination_sum(candidates, target):
    """
    Find combinations that sum to target.

    Without pruning: Try all combinations (exponential)
    With pruning: Skip branches that exceed target early
    """
    result = []
    candidates.sort()  # Sort for pruning

    def backtrack(start, current, current_sum):
        if current_sum == target:
            result.append(current[:])
            return

        for i in range(start, len(candidates)):
            num = candidates[i]

            # PRUNE: If current sum + num exceeds target,
            # all future numbers will too (since sorted)
            if current_sum + num > target:
                break  # Skip entire remaining branch

            current.append(num)
            backtrack(i, current, current_sum + num)
            current.pop()

    backtrack(0, [], 0)
    return result

# Pruning impact:
# candidates = [2,3,5], target = 8
# Without pruning: Explores ~100 states
# With pruning: Explores ~20 states (5x speedup)

def subsets_with_duplicates(nums):
    """
    Generate unique subsets when input has duplicates.

    Key: Sort and skip consecutive duplicates at same level.
    """
    nums.sort()
    result = []

    def backtrack(start, current):
        result.append(current[:])

        for i in range(start, len(nums)):
            # Skip duplicate elements at same recursion level
            if i > start and nums[i] == nums[i-1]:
                continue

            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

# Input: [1, 2, 2]
# Without dedup: [[],[1],[1,2],[1,2,2],[1,2],[2],[2,2],[2]]
# With dedup:    [[],[1],[1,2],[1,2,2],[2],[2,2]]

def word_break_all(s, word_dict):
    """
    Find all ways to break string using dictionary words.

    Problem: Same substring processed multiple times
    Solution: Memoize results by substring
    """
    memo = {}

    def backtrack(start):
        if start in memo:
            return memo[start]

        if start == len(s):
            return [[]]

        result = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_dict:
                # Found valid word - recurse on rest
                for rest in backtrack(end):
                    result.append([word] + rest)

        memo[start] = result
        return result

    return [' '.join(words) for words in backtrack(0)]

# s = "catsanddog", dict = ["cat","cats","and","sand","dog"]
# Without memo: O(2^n) - exponential
# With memo: O(n^3) - polynomial

def sudoku_solver(board):
    """
    Solve Sudoku with constraint propagation.

    Instead of trying all numbers 1-9,
    maintain set of possible values for each cell.
    """
    # Possible values for each cell
    possible = [[set(range(1, 10)) if board[i][j] == 0 else set()
                 for j in range(9)] for i in range(9)]

    # Remove impossibilities based on initial state
    for i in range(9):
        for j in range(9):
            if board[i][j] != 0:
                propagate_constraints(board, possible, i, j, board[i][j])

    def backtrack():
        # Find cell with fewest possibilities (most constrained)
        min_choices = 10
        best_cell = None

        for i in range(9):
            for j in range(9):
                if board[i][j] == 0 and len(possible[i][j]) < min_choices:
                    min_choices = len(possible[i][j])
                    best_cell = (i, j)

        if best_cell is None:
            return True  # Solved

        i, j = best_cell

        # Try each possible value
        for num in list(possible[i][j]):
            board[i][j] = num
            old_possible = [row[:] for row in possible]

            if propagate_constraints(board, possible, i, j, num):
                if backtrack():
                    return True

            board[i][j] = 0
            possible[:] = old_possible

        return False

    return backtrack()

# Most constrained first: Huge pruning improvement
# Random order: ~100,000 states
# Most constrained: ~1,000 states (100x faster)