回溯算法 (Backtracking)

LeetCodeBacktracking回溯算法

回溯算法 (Backtracking)

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来尝试新的候选解。

基础概念

回溯算法框架

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

决策树示例

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

经典问题

1. 全排列

LeetCode 46 - Permutations

输入: [1,2,3]
决策树:
         []
    /    |     \
   [1]  [2]    [3]
  /  \   |  \   |  \
[1,2][1,3][2,1][2,3][3,1][3,2]
  |     |    |    |    |    |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
def permute(nums):
    def backtrack(first = 0):
        if first == n:
            output.append(nums[:])
        for i in range(first, n):
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]
            
    n = len(nums)
    output = []
    backtrack()
    return output

2. 子集

LeetCode 78 - Subsets

输入: [1,2,3]
决策树:
                  []
         /        |          \
      [1]        [2]        [3]
    /     \        \
[1,2]    [1,3]    [2,3]
   |
[1,2,3]

输出: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
def subsets(nums):
    def backtrack(start, curr):
        output.append(curr[:])
        for i in range(start, len(nums)):
            curr.append(nums[i])
            backtrack(i + 1, curr)
            curr.pop()
    
    output = []
    backtrack(0, [])
    return output

3. N皇后

LeetCode 51 - N-Queens

N=4的一个解:
. Q . .    [1]
. . . Q    [3]
Q . . .    [0]
. . Q .    [2]

决策过程:
1. 第一行放Q: . Q . .
2. 检查可用位置
3. 继续下一行
4. 如果无解则回溯
def solveNQueens(n):
    def createBoard():
        return ["." * n for _ in range(n)]
    
    def backtrack(row, diagonals, anti_diagonals, cols, state):
        if row == n:
            solutions.append(state[:])
            return
        
        for col in range(n):
            curr_diagonal = row - col
            curr_anti_diagonal = row + col
            
            if (col in cols or 
                curr_diagonal in diagonals or 
                curr_anti_diagonal in anti_diagonals):
                continue
                
            cols.add(col)
            diagonals.add(curr_diagonal)
            anti_diagonals.add(curr_anti_diagonal)
            state[row] = state[row][:col] + "Q" + state[row][col+1:]
            
            backtrack(row + 1, diagonals, anti_diagonals, cols, state)
            
            cols.remove(col)
            diagonals.remove(curr_diagonal)
            anti_diagonals.remove(curr_anti_diagonal)
            state[row] = state[row][:col] + "." + state[row][col+1:]
    
    solutions = []
    empty_board = createBoard()
    backtrack(0, set(), set(), set(), empty_board)
    return solutions

4. 组合总和

LeetCode 39 - Combination Sum

输入: candidates = [2,3,6,7], target = 7

决策树:
                     7
          /      /    \      \
         5      4     1      0
       / \     /\     |
      3   2   1  -1   -2
     /
    1
def combinationSum(candidates, target):
    def backtrack(remain, comb, start):
        if remain == 0:
            result.append(list(comb))
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                continue
            
            comb.append(candidates[i])
            backtrack(remain - candidates[i], comb, i)
            comb.pop()
    
    result = []
    candidates.sort()
    backtrack(target, [], 0)
    return result

高级应用

1. 图着色问题

图的表示:
1 --- 2
|     |
3 --- 4

颜色分配:
1: 红
2: 蓝
3: 蓝
4: 红

2. 数独求解

数独板:
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

3. 正则表达式匹配

模式匹配:
text:     aab
pattern:  c*a*b

匹配过程:
1. c* → 跳过
2. a* → 匹配aa
3. b  → 匹配b

常见技巧

  1. 路径记录
  2. 状态标记
  3. 剪枝优化
  4. 约束传播
  5. 启发式搜索

相关题目