Detailed Explanation of Backtracking Algorithm

Core Idea and Principles

The backtracking algorithm is essentially a trial-and-error approach: by trying all possible paths, we find all solutions that satisfy the conditions. When we discover that the current path is not feasible, we "backtrack" to the previous decision point and try another choice. This algorithm is particularly suitable for solving problems related to permutations and combinations, path searching, and constraint satisfaction.

The essence of backtracking algorithm: traversing the decision tree, where each leaf node represents a possible solution. By systematically exploring all possible choices, we can find all answers that meet the conditions.

Relationship between Backtracking and Depth-First Search (DFS)

Backtracking algorithm is actually an application of DFS, but backtracking emphasizes the concept of "state reset": whenever we finish exploring a branch, we need to restore the state to explore other branches. This is the so-called "make a choice" and "undo a choice" mechanism.

Exploration process: decision tree → choose → recurse → undo choice → backtrack

Construction and Traversal of Decision Trees

In backtracking problems, the decision tree is key to understanding and solving the problem. Each node represents a state, and each edge represents a choice.

Three Key Elements of a Decision Tree

Path: All choices made from the root node to the current node (decisions already made)
Choice list: Choices available at the current node (unexplored possibilities)
End condition: Conditions that indicate a leaf node has been reached, where no further choices can be made (recursive termination condition)

Taking the permutation problem as an example, for the array [1, 2, 3], the decision tree is shown as follows:

permutation

At each node:

The path is the numbers already chosen (e.g., [2] at Node 2)
The choice list is the remaining numbers that can be chosen (e.g., [1,3] at Node 2)
The end condition is when the choice list is empty, at which point a permutation is completed

Two Types of Backtracking Problems

When approaching a backtracking problem, it's crucial to identify which of the two primary paradigms to use. Let's explore both types in depth, with step-by-step guidance on how to apply each approach.

Problems That Must Use All Options

This type of problem requires us to consider all possible choices in the decision process, without ignoring any options. These problems typically involve finding all permutations or arrangements where each element must be used exactly once.

Step-by-Step Approach for Full-Selection Backtracking:

Identify the decision space: Determine what choices are available at each step and how they change as decisions are made.
Define the state representation: Establish how to track the current path and remaining choices.
Implement state tracking: Use appropriate data structures (arrays, sets, etc.) to mark which options have been used.
Define termination conditions: Determine when a complete solution has been found.
Implement the choice-making process: For each available choice:
- Make the choice and update the state
- Recursively explore further choices
- Undo the choice to restore the previous state
Handle constraints: Implement logic to skip invalid choices early.

Example: Permutation Problem

LeetCode Problem 46: Permutations

Description: Given an array nums of distinct integers, return all possible permutations.

permutation

Step-by-Step Application of Full-Selection Backtracking:

For example, with input [1,2,3], we would:

Define our state representation:
- path: Current permutation being built (initially empty [])
- used: Track which elements have been used (initially [False, False, False])
Begin backtracking from the root:
- At each level, we must choose one unused number from the array
- For level 1, we have three choices: 1, 2, or 3
Make the first choice (e.g., choose 1):
- Update path: [1]
- Update used: [True, False, False]
- Recurse to the next level
At the second level, we now have two choices: 2 or 3
- If we choose 2:
  - Update path: [1, 2]
  - Update used: [True, True, False]
  - Recurse to the next level
At the third level, we only have one choice: 3
- Update path: [1, 2, 3]
- Update used: [True, True, True]
- We've reached a leaf node (all elements used)
- Add [1, 2, 3] to the result
- Backtrack by undoing the last choice
Undo the choice of 3:
- Update path: [1, 2]
- Update used: [True, True, False]
- No more unused elements at this level, backtrack further
Undo the choice of 2:
- Update path: [1]
- Update used: [True, False, False]
- Try the other choice (3) at this level

And so on until we've explored all possible permutations.

def permute(nums):
    result = []
    path = []
    used = [False] * len(nums)
 
    def backtrack():
        # End condition: choice list is empty, i.e., path length equals nums length
        if len(path) == len(nums):
            result.append(path.copy())  # Note: need to copy here, otherwise it will be affected by subsequent operations on path
            return
 
        # Traverse the choice list
        for i in range(len(nums)):
            # Skip used elements
            if used[i]:
                continue
 
            # Make a choice
            path.append(nums[i])
            used[i] = True
 
            # Recurse to the next level of the decision tree
            backtrack()
 
            # Undo the choice
            path.pop()
            used[i] = False
 
    backtrack()
    return result

This code perfectly demonstrates the core idea of backtracking:

Maintain a path to record choices made
Use a used array to track which elements have been used
Try all unused elements at each decision level
Undo choices after each recursion to try other possibilities

Example: Word Search

LeetCode Problem 79: Word Search

Description: Given an m x n grid of characters and a word, return true if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells.

Step-by-Step Application for Grid Search:

Define the state:
- Current position in the grid (row, column)
- Current index in the target word
- Visited cells (to avoid reuse)
For each starting position in the grid:
- If the character matches the first letter of the word, start the search
- Temporarily mark the cell as visited
- Explore all four directions (up, down, left, right)
- Restore the cell's original value when backtracking
Terminate the search when:
- We've matched all characters in the word (success)
- We go out of bounds or find a non-matching character (failure)
Backtrack after exploring each direction, regardless of success or failure

def exist(board, word):
    rows, cols = len(board), len(board[0])
 
    def dfs(r, c, index):
        # If the index reaches the word length, the complete word has been found
        if index == len(word):
            return True
 
        # Boundary check and character match check
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            board[r][c] != word[index]):
            return False
 
        # Mark the current cell as visited (to avoid reuse)
        temp = board[r][c]
        board[r][c] = '#'  # Temporary modification to avoid revisiting
 
        # Explore four directions
        found = (dfs(r+1, c, index+1) or
                 dfs(r-1, c, index+1) or
                 dfs(r, c+1, index+1) or
                 dfs(r, c-1, index+1))
 
        # Restore the cell
        board[r][c] = temp
 
        return found
 
    # Try each cell as a starting point
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
 
    return False

This example demonstrates the application of backtracking in grid search problems:

At each position, we explore four possible directions
We use temporary modification and restoration to prevent revisiting
When an unfeasible path is discovered, we backtrack to the previous step to try other directions

Problems Where Some Options Can Be Skipped

This type of problem has a binary choice at each node: select the current element or skip it. Unlike full-selection problems, not all elements need to be used in the final solution.

Step-by-Step Approach for Binary Choice Backtracking:

Recognize the binary nature: Understand that for each element, you have exactly two choices: include it or exclude it.
Define a processing order: Usually, elements are processed in a specific order (often left to right in an array).
Track the current solution state: Maintain a collection of chosen elements.
Process elements sequentially:
- For each element, first explore the "include" path
- Then explore the "exclude" path
- Or implicitly exclude by only considering elements from the current index onward
Collect results either at termination points or at each state (depending on the problem).

Example: Subset problem

LeetCode Problem 78: Subsets

Description: Given an integer array nums of unique elements, return all possible subsets (the power set).

subset

Step-by-Step Application of Binary Choice Backtracking:

For input [1,2,3], we would:

Define our state representation:
- subset: Current subset being built (initially empty [])
- index: Current position in the array we're deciding on
Begin with the empty subset (this is always a valid subset)
- Add [] to the result
For the first element (1), we have two choices:
- Include 1: Add 1 to our subset, giving [1]
- Exclude 1: Leave the subset as is, still []
For the second element (2), we again have two choices for each previous state:
- If we included 1:
  - Include 2: Add 2 to [1], giving [1,2]
  - Exclude 2: Leave as [1]
- If we excluded 1:
  - Include 2: Add 2 to [], giving [2]
  - Exclude 2: Leave as []
For the third element (3), we continue the pattern
- For [1,2]: We can include 3 to get [1,2,3] or exclude 3 to keep [1,2]
- For [1]: We can include 3 to get [1,3] or exclude 3 to keep [1]
- For [2]: We can include 3 to get [2,3] or exclude 3 to keep [2]
- For []: We can include 3 to get [3] or exclude 3 to keep []
Our final result includes all unique subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

The implementation can be done in two ways:

Method 1: Iterative for-loop with implicit "don't choose" option

def subsets(nums):
    result = []
    subset = []
 
    def backtrack(index):
        # Every path is a valid subset
        result.append(subset.copy())
 
        # Try from the current index onwards
        for i in range(index, len(nums)):
            # Choose the current number
            subset.append(nums[i])
 
            # Recurse to the next position
            backtrack(i + 1)
 
            # Undo the choice, try without the current number
            subset.pop()
 
    backtrack(0)
    return result

This method traverses all possible subsets, with the key being:

Each recursive call considers all elements starting from the current index
For each element, we make a choice of "add" or "don't add"
We don't need to explicitly represent the "don't choose" decision, as we implicitly implement it by skipping certain indices

Method 2: Explicit binary choice

def subsets_binary(nums):
    result = []
    subset = []
 
    def backtrack(index):
        if index == len(nums):
            result.append(subset.copy())
            return
 
        # Choose the current element
        subset.append(nums[index])
        backtrack(index + 1)
 
        # Don't choose the current element
        subset.pop()
        backtrack(index + 1)
 
    backtrack(0)
    return result

This implementation more intuitively shows the essence of binary decision:

For each element, we have two paths: choose it or don't choose it
Both paths continue to recurse, but with different states
This method forms a complete binary decision tree

Key Difference Between the Two Implementations:

Method 1 (Iterative): We make one recursive call per element we want to include, and implicitly exclude elements by not considering them. This is more space-efficient as it generates fewer recursive calls.
Method 2 (Binary): We explicitly make two recursive calls for every element (include or exclude), resulting in exactly 2ⁿ leaf nodes for n elements. This is conceptually clearer but generates more recursive calls.

General Templates for Backtracking

Based on the problem type, we can summarize two backtracking templates:

Full-Selection Backtracking Template

def backtracking(choice_list):
    result = []
    path = []
 
    def backtrack(choice_list, path):
        if end_condition_met:
            result.append(path.copy())
            return
 
        for choice in choice_list:
            if invalid_choice:
                continue
 
            # Make a choice
            path.append(choice)
 
            # Recurse
            backtrack(choice_list, path)
 
            # Undo the choice
            path.pop()
 
    backtrack(choice_list, path)
    return result

Binary Choice Backtracking Template

def backtracking(nums):
    result = []
    path = []
 
    def backtrack(index):
        # Possibly record the result here
        result.append(path.copy())
 
        for i in range(index, len(nums)):
            # Make a choice - choose the current element
            path.append(nums[i])
 
            # Recurse to the next level
            backtrack(i + 1)
 
            # Undo the choice
            path.pop()
 
    backtrack(0)
    return result

Optimization Techniques for Backtracking

Pruning

Pruning is a key technique to improve backtracking efficiency by determining in advance that a certain path cannot produce valid results, thus avoiding unnecessary searches.

Example: Combination Sum Problem

LeetCode Problem 39: Combination Sum

Description: Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

def combinationSum(candidates, target):
    result = []
    path = []
 
    # Sort first for easier pruning
    candidates.sort()
 
    def backtrack(start, target):
        if target == 0:
            result.append(path.copy())
            return
 
        for i in range(start, len(candidates)):
            # Pruning: if the current element is already larger than the target,
            # later elements are even larger and cannot satisfy the requirement
            if candidates[i] > target:
                break
 
            path.append(candidates[i])
 
            # Because elements can be reused, still start from i
            backtrack(i, target - candidates[i])
 
            path.pop()
 
    backtrack(0, target)
    return result

Key optimization points in this example:

Sort the candidate array to ensure smaller elements are tried first
When the current element already exceeds the target value, break out of the loop to avoid subsequent ineffective attempts

Avoiding Duplicates

In some problems, different paths may produce the same result. How to avoid duplicates is an important issue.

Example: Subsets II

LeetCode Problem 90: Subsets II

Description: Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

def subsetsWithDup(nums):
    result = []
    path = []
 
    # Sort to identify duplicate elements
    nums.sort()
 
    def backtrack(start):
        result.append(path.copy())
 
        for i in range(start, len(nums)):
            # Avoid duplicates: if the current element is the same as the previous one
            # and the previous one is not used, skip
            if i > start and nums[i] == nums[i-1]:
                continue
 
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()
 
    backtrack(0)
    return result

This example demonstrates key techniques for handling duplicate elements:

First sort to make identical elements adjacent
In the same decision level, skip identical elements that have already been considered

Complexity Analysis of Backtracking

The time complexity of backtracking algorithms is usually related to the size of the solution space.

Time Complexity

For permutation problems, the time complexity is approximately O(n!), as there are n! possible permutations. For subset problems, the time complexity is approximately O(2^n), as each element has two states: selected or not selected.

Space Complexity

Space complexity is mainly determined by the depth of the recursion stack and the space for storing results:

The depth of the recursion stack is usually O(n), where n is the problem size
The space for storing results depends on the number and size of solutions

Advanced Backtracking Problem Analysis

N-Queens problem

LeetCode Problem 51: N-Queens

Description: The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

def solveNQueens(n):
    result = []
 
    # Initialize the board
    board = [['.' for _ in range(n)] for _ in range(n)]
 
    # For checking conflicts in columns and diagonals
    cols = set()
    posDiag = set()  # r + c
    negDiag = set()  # r - c
 
    def backtrack(r):
        if r == n:
            # Found a valid solution, add to results
            copy = [''.join(row) for row in board]
            result.append(copy)
            return
 
        for c in range(n):
            # Check for conflicts
            if c in cols or (r + c) in posDiag or (r - c) in negDiag:
                continue
 
            # Place a queen
            board[r][c] = 'Q'
            cols.add(c)
            posDiag.add(r + c)
            negDiag.add(r - c)
 
            # Recurse to the next row
            backtrack(r + 1)
 
            # Backtrack, remove the queen
            board[r][c] = '.'
            cols.remove(c)
            posDiag.remove(r + c)
            negDiag.remove(r - c)
 
    backtrack(0)
    return result

This example demonstrates the application of backtracking in constraint satisfaction problems:

Use three sets to track columns and diagonals where queens have been placed
Try all possible column positions in each row
Skip the current choice when a conflict is found
Record the result when queens have been successfully placed in all rows

Summary

Backtracking algorithm is a powerful tool for solving permutation and combination, path search, and constraint satisfaction problems:

Fundamental concept: Systematic trial and error, exploring all possible solutions
Applicable scenarios: Combination problems requiring enumeration of all possible solutions
Core steps: Choose → Recurse → Undo choice
Efficiency improvements: Pruning, avoiding duplicates, choosing appropriate data structures
Code characteristics: Recursive functions, state restoration mechanism, result collection

The key to mastering the backtracking algorithm lies in:

Correctly identifying the structure of the problem's solution space
Designing appropriate state representation and transition methods
Implementing efficient pruning strategies
Understanding the mechanism of "making choices" and "undoing choices"

How to Choose the Appropriate Backtracking Type

Before solving a problem, we often need to determine whether to use full-selection backtracking or binary choice backtracking. This decision has an important impact on implementation efficiency and code structure.

Scenarios Suitable for Full-Selection Backtracking

Full-selection backtracking (must use all options) is typically suitable for the following scenarios:

Permutation problems: Need to consider the order of elements, each element must be used once
- Permutation problem (LeetCode 46)
- Permutations with duplicate elements (LeetCode 47)
Path search problems: Need to go from start to end under specific constraints
- Unique Paths III (LeetCode 980)
- Word Search (LeetCode 79)
Multi-choice decision problems: Each position must select one from multiple options

Judgment criteria:

Need to try multiple possible choices (not just choose or not choose)
Each position must make a choice, cannot be skipped
Usually need auxiliary data structures (such as a used array) to track options already used

Scenarios Suitable for Binary Choice Backtracking

Binary choice backtracking (can skip some options) is typically suitable for the following scenarios:

Subset/combination problems: Make include or exclude decisions for each element
Selection problems: Select or not select from a series of items
Selection under constraints: Make selections under certain constraints

Judgment criteria:

The essence of the problem is making binary decisions for each element (select or not select)
The size of the result set is usually 2^n level (for n elements)
No need to consider all permutations of the elements, only care about whether they are included

Different Implementation Methods for the Same Problem

Interestingly, many problems can be implemented in both ways. Taking the subset problem as an example:

Binary choice implementation (explicitly representing select/not select):

def subsets_binary(nums):
    result = []
    subset = []
 
    def backtrack(index):
        if index == len(nums):
            result.append(subset.copy())
            return
 
        # Choose the current element
        subset.append(nums[index])
        backtrack(index + 1)
 
        # Don't choose the current element
        subset.pop()
        backtrack(index + 1)
 
    backtrack(0)
    return result

Full-selection backtracking implementation (implicitly representing not select):

def subsets_iterative(nums):
    result = []
    subset = []
 
    def backtrack(start):
        # Each state is a valid subset
        result.append(subset.copy())
 
        for i in range(start, len(nums)):
            # Choose the current element
            subset.append(nums[i])
            backtrack(i + 1)
            subset.pop()
 
    backtrack(0)
    return result

Considerations when choosing:

Code conciseness:
- Binary choice implementation usually has clearer logic, directly reflecting the "select or not select" idea
- Full-selection implementation may have more concise code for certain problems
Efficiency comparison:
- Binary choice implementation generates a fixed 2^n recursive calls
- Full-selection implementation controls the number of recursions through loops, which may be more efficient
Handling duplicate problems:
- Full-selection implementation makes it easier to handle problems with duplicate elements (by sorting and skipping identical elements)
- Binary choice implementation requires additional logic to handle duplicate elements
Problem characteristics:
- If the problem essentially requires a "multiple-choice" decision pattern, full-selection is more appropriate
- If the problem is essentially a "want or don't want" binary decision, binary choice is more intuitive

Case Analysis: Combination Sum Problem

The Combination Sum problem (LeetCode Problem 39: Combination Sum) requires finding all combinations from a candidate array that sum to a target value:

Full-selection implementation (suitable for this problem):

def combinationSum(candidates, target):
    result = []
    combination = []
 
    def backtrack(start, remain):
        if remain == 0:
            result.append(combination.copy())
            return
        if remain < 0:
            return
 
        for i in range(start, len(candidates)):
            combination.append(candidates[i])
            # Allow reuse of elements, so still start from i
            backtrack(i, remain - candidates[i])
            combination.pop()
 
    backtrack(0, target)
    return result

This problem is suitable for full-selection backtracking because:

We need to select from multiple candidates, not just "select or not select" a single element
It allows reusing elements, which requires special handling of indices
Full-selection implementation facilitates pruning optimization (such as sorting the candidate array)

Mastering the judgment criteria and characteristics of both backtracking methods can help us solve combination optimization problems more efficiently. Choosing the appropriate backtracking strategy based on problem characteristics can often significantly improve the efficiency and clarity of the solution.

Detailed Explanation of Backtracking Algorithm

On this page