学习笔记

回溯算法 ​

#算法 · #回溯 · #剪枝 · #DFS · #排列组合 · #N皇后

回溯算法（Backtracking）是一种通过探索所有可能的候选解来找出所有解（或最优解）的算法。当发现候选解不可能产生有效解时，及时"回溯"（撤销选择），避免无效搜索。

核心思想 ​

回溯三要素 ​

1. 路径：已经做出的选择
2. 选择列表：当前可以做的选择
3. 结束条件：到达决策树底层，无法再做选择

通用框架 ​

python
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        # 做选择
        路径.add(选择)
        # 递归
        backtrack(路径, 新的选择列表)
        # 撤销选择（回溯）
        路径.remove(选择)
决策树示意（全排列 [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]

一、子集（Subsets） ​

go
// 无重复元素
func subsets(nums []int) [][]int {
    var result [][]int
    var path []int
    var backtrack func(start int)
    backtrack = func(start int) {
        // 每个节点都是有效解
        subset := make([]int, len(path))
        copy(subset, path)
        result = append(result, subset)

        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]  // 回溯
        }
    }
    backtrack(0)
    return result
}

// 有重复元素 → 排序 + 跳过重复
func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    var result [][]int
    var path []int
    var backtrack func(start int)
    backtrack = func(start int) {
        subset := make([]int, len(path))
        copy(subset, path)
        result = append(result, subset)

        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] {
                continue  // 跳过同一层的重复元素
            }
            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }
    backtrack(0)
    return result
}

二、组合（Combinations） ​

go
// C(n,k)：从 n 个数中选 k 个
func combine(n, k int) [][]int {
    var result [][]int
    var path []int
    var backtrack func(start int)
    backtrack = func(start int) {
        if len(path) == k {
            comb := make([]int, k)
            copy(comb, path)
            result = append(result, comb)
            return
        }
        // 剪枝：剩余元素不足以凑够 k 个
        for i := start; i <= n-(k-len(path))+1; i++ {
            path = append(path, i)
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }
    backtrack(1)
    return result
}

// 组合总和（可重复选，和 = target）
func combinationSum(candidates []int, target int) [][]int {
    var result [][]int
    var path []int
    var backtrack func(start, remain int)
    backtrack = func(start, remain int) {
        if remain < 0 {
            return
        }
        if remain == 0 {
            comb := make([]int, len(path))
            copy(comb, path)
            result = append(result, comb)
            return
        }
        for i := start; i < len(candidates); i++ {
            path = append(path, candidates[i])
            backtrack(i, remain-candidates[i])  // 注意是 i 不是 i+1（可重复）
            path = path[:len(path)-1]
        }
    }
    backtrack(0, target)
    return result
}

三、排列（Permutations） ​

go
// 全排列（无重复）
func permute(nums []int) [][]int {
    var result [][]int
    var path []int
    used := make([]bool, len(nums))

    var backtrack func()
    backtrack = func() {
        if len(path) == len(nums) {
            perm := make([]int, len(path))
            copy(perm, path)
            result = append(result, perm)
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            backtrack()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    backtrack()
    return result
}

// 全排列（有重复）→ 排序 + 剪枝
func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    var result [][]int
    var path []int
    used := make([]bool, len(nums))

    var backtrack func()
    backtrack = func() {
        if len(path) == len(nums) {
            perm := make([]int, len(path))
            copy(perm, path)
            result = append(result, perm)
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            // 关键剪枝：相同数字，前一个没用过 → 跳过
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            backtrack()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    backtrack()
    return result
}

四、N 皇后 ​

go
func solveNQueens(n int) [][]string {
    var result [][]string
    // board[row] = col：第 row 行的皇后放在第 col 列
    board := make([]int, n)
    cols := make([]bool, n)
    diag1 := make([]bool, 2*n)  // 主对角线：row-col+n
    diag2 := make([]bool, 2*n)  // 副对角线：row+col

    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            result = append(result, generateBoard(board, n))
            return
        }
        for col := 0; col < n; col++ {
            d1, d2 := row-col+n, row+col
            if cols[col] || diag1[d1] || diag2[d2] {
                continue
            }
            board[row] = col
            cols[col], diag1[d1], diag2[d2] = true, true, true
            backtrack(row + 1)
            cols[col], diag1[d1], diag2[d2] = false, false, false
        }
    }
    backtrack(0)
    return result
}

func generateBoard(board []int, n int) []string {
    rows := make([]string, n)
    for i, col := range board {
        row := make([]byte, n)
        for j := range row {
            if j == col {
                row[j] = 'Q'
            } else {
                row[j] = '.'
            }
        }
        rows[i] = string(row)
    }
    return rows
}

五、数独求解 ​

go
func solveSudoku(board [][]byte) {
    var backtrack func() bool
    backtrack = func() bool {
        for i := 0; i < 9; i++ {
            for j := 0; j < 9; j++ {
                if board[i][j] != '.' {
                    continue
                }
                for num := byte('1'); num <= '9'; num++ {
                    if isValid(board, i, j, num) {
                        board[i][j] = num
                        if backtrack() {
                            return true
                        }
                        board[i][j] = '.'  // 回溯
                    }
                }
                return false  // 1-9 都试过，都不行
            }
        }
        return true  // 全部填完
    }
    backtrack()
}

func isValid(board [][]byte, row, col int, num byte) bool {
    for i := 0; i < 9; i++ {
        if board[row][i] == num || board[i][col] == num {
            return false
        }
    }
    // 3x3 宫
    r, c := (row/3)*3, (col/3)*3
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            if board[r+i][c+j] == num {
                return false
            }
        }
    }
    return true
}

六、剪枝技巧 ​

技巧说明示例
可行性剪枝当前状态不可能到达解组合总和 remain<0
最优性剪枝当前状态不可能优于最优解分支限界
对称性剪枝避免枚举对称等价解N 皇后镜像
排序 + 跳过重复去掉重复解全排列 II
记忆化避免重复搜索同一状态Minimax + memo

七、经典 Hard 题 ​

7.1 解数独（Sudoku Solver） ​

go
func solveSudoku(board [][]byte) {
    var rows, cols [9][9]bool // rows[i][num] = 第 i 行是否已有 num+1
    var boxes [3][3][9]bool   // boxes[i][j][num] = 第(i,j)个3x3宫

    // 初始化已有数字
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] != '.' {
                num := board[i][j] - '1'
                rows[i][num] = true
                cols[j][num] = true
                boxes[i/3][j/3][num] = true
            }
        }
    }

    var backtrack func(r, c int) bool
    backtrack = func(r, c int) bool {
        if r == 9 { return true } // 全部填完
        if c == 9 { return backtrack(r+1, 0) }
        if board[r][c] != '.' { return backtrack(r, c+1) }

        for num := byte(0); num < 9; num++ {
            if rows[r][num] || cols[c][num] || boxes[r/3][c/3][num] {
                continue // 剪枝：数字已被占用
            }
            // 做选择
            board[r][c] = '1' + num
            rows[r][num], cols[c][num] = true, true
            boxes[r/3][c/3][num] = true

            if backtrack(r, c+1) { return true }

            // 撤销
            board[r][c] = '.'
            rows[r][num], cols[c][num] = false, false
            boxes[r/3][c/3][num] = false
        }
        return false
    }
    backtrack(0, 0)
}
text
解数独的剪枝策略:
  1. 可行性剪枝: 行/列/宫已有数字则跳过 (最核心，将 9^81 缩减到可计算范围)
  2. 约束传播: 每次选择前，先找到候选数最少的空格 (优化版可用优先队列)
  3. 不剪枝的话: 9^81 种可能 → 宇宙的年龄都不够跑

7.2 单词搜索（Word Search） ​

go
func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])

    var dfs func(i, j, k int) bool
    dfs = func(i, j, k int) bool {
        if k == len(word) { return true }
        if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k] {
            return false
        }

        // 原地标记（节省 visited 矩阵空间）
        tmp := board[i][j]
        board[i][j] = '#'

        // 四个方向搜索
        found := dfs(i+1, j, k+1) || dfs(i-1, j, k+1) ||
                 dfs(i, j+1, k+1) || dfs(i, j-1, k+1)

        board[i][j] = tmp // 回溯
        return found
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(i, j, 0) { return true }
        }
    }
    return false
}
text
单词搜索剪枝三件套:
  1. 字符不匹配 → 立即返回 (最有效的可行性剪枝)
  2. 原地标记替代 visited 矩阵 → O(1) 额外空间
  3. 回溯恢复 → 确保不影响其他搜索路径

7.3 分割回文串（Palindrome Partitioning） ​

go
func partition(s string) [][]string {
    var res [][]string
    var path []string

    // 预处理: isPal[i][j] = s[i:j+1] 是否为回文 (DP)
    n := len(s)
    isPal := make([][]bool, n)
    for i := range isPal {
        isPal[i] = make([]bool, n)
    }
    // dp: s[i]==s[j] && (j-i<=1 || isPal[i+1][j-1])
    for j := 0; j < n; j++ {
        for i := 0; i <= j; i++ {
            if s[i] == s[j] && (j-i <= 1 || isPal[i+1][j-1]) {
                isPal[i][j] = true
            }
        }
    }

    var backtrack func(start int)
    backtrack = func(start int) {
        if start == n {
            res = append(res, append([]string{}, path...))
            return
        }
        for end := start; end < n; end++ {
            if isPal[start][end] { // 剪枝: 不是回文的分割直接跳过
                path = append(path, s[start:end+1])
                backtrack(end + 1)
                path = path[:len(path)-1]
            }
        }
    }
    backtrack(0)
    return res
}
mermaid
flowchart TB
    subgraph Pruning["分割回文串的剪枝"]
        A["s = 'aab'"] --> B{"start=0"}
        B --> C["end=0: 'a' 是回文 ✅<br/>→ 递归 start=1"]
        C --> D{"start=1"}
        D -->|"end=1: 'a' ✅"| E["→ start=2<br/>end=2: 'b' ✅<br/>→ ['a','a','b']"]
        D -->|"end=2: 'ab' ❌"| F["剪枝跳过"]
        B --> G["end=1: 'aa' ✅<br/>→ 递归 start=2"]
        G --> H["end=2: 'b' ✅<br/>→ ['aa','b']"]
        B --> I["end=2: 'aab' ❌<br/>剪枝跳过"]
    end

    style F fill:#f44336,color:#fff
    style I fill:#f44336,color:#fff

7.4 回溯剪枝对比总结 ​

mermaid
flowchart LR
    subgraph Before["剪枝前：搜索树 9^81"]
        N1["..."] --- N2["..."] --- N3["..."]
    end

    subgraph After["剪枝后：行/列/宫约束 → ~10^4 个节点"]
        A1["仅少量分支"] --- A2["绝大多数被剪掉"]
    end

    Before -.->|"剪枝率 > 99.999%"| After
题目暴力搜索空间剪枝后关键剪枝策略
解数独9^81~10^4行/列/宫可行性
N 皇后n!~n!列/对角线可行性
单词搜索4^L×mn~4^L字符匹配 + 原地标记
分割回文串2^n~2^nDP 预判回文

回溯 / DFS / 动态规划 对比 ​

维度回溯DFS（图）动态规划
问题求所有解遍历所有节点求最优解
状态路径 + 选择列表当前节点 + visiteddp 表
重复子问题有（不用 memo 则重复）有（用 visited 去重）有（核心，必须利用）
撤销操作✅ 必须❌ visited 不回退（或回退）❌
典型问题排列/组合/N皇后迷宫/岛屿背包/LCS

参考 ​

批注模式

💬 文章评论

暂无评论，来说点什么吧 👇

编程学习笔记

Copyright © 2026