06.算法——回溯

算法专题：回溯（Backtracking）

相关数据结构实现用go语言实现

相关代码做题合集：https://github.com/longpi1/algorithm-pattern

1. 引言

在计算机科学中，回溯（Backtracking）是一种常用的算法范式，用于在所有（或部分）可能的解中搜索问题的解。它是一种通过尝试所有可能路径来找到解决方案的系统化方法。当遇到死路或者发现当前路径不可能通向有效解时，算法会“回溯”到上一个决策点，并尝试另一条路径。

回溯算法本质上是一种深度优先搜索（DFS），它在问题的解空间树（State-Space Tree）中进行搜索。

2. 回溯的核心思想

回溯算法的核心思想可以概括为“试探”和“撤销”：

  1. 选择（Choose）：在当前状态下，选择一个可能的下一步。
  2. 探索（Explore）：基于这个选择，进入新的状态。
  3. 判断（Judge）：
    • 如果新状态满足问题的解条件，则找到了一个解。
    • 如果新状态无法继续（即进入死路）或者已经不符合约束条件（即此路不通），则放弃此路径。
  4. 回溯（Unchoose/Backtrack）：撤销上一步的选择，返回到上一个状态，尝试另一个不同的选择。

这个过程就像在一个迷宫中寻找出口：你选择一条路走，如果走不通就退回来，再尝试另一条路，直到找到出口或者尝试完所有路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
回溯法（backtrack）常用于遍历列表所有子集，是 DFS 深度搜索一种，一般用于全排列，穷尽所有可能，遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!)，它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

## 模板

```go
result = []
func backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择
```

3. 回溯算法的特点

  • 递归实现：通常通过递归函数实现，函数参数代表当前状态。
  • 状态管理：在每次选择时修改当前状态，在回溯时恢复状态。这是回溯算法的关键。
  • 剪枝（Pruning）：在搜索过程中，如果发现当前路径不可能通向有效解，就立即停止对该路径的进一步探索，从而大大减少搜索空间，提高效率。
  • 解空间树：问题的所有可能解形成一个树形结构，回溯算法就是在这个树上进行深度优先遍历。

4. 适用场景

回溯算法常用于解决以下类型的问题：

  • 组合问题：从给定集合中找出所有满足条件的组合（如子集、组合总和）。
  • 排列问题：从给定集合中找出所有可能的排列。
  • 子集问题：找出给定集合的所有子集。
  • 棋盘游戏：如N皇后问题、数独。
  • 路径搜索：如迷宫问题、旅行商问题（决策版本）。

5. 回溯算法通用模板 (Go语言实现)

一个典型的回溯函数通常包含以下几个部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// result 存储所有找到的有效解
var result [][]int // 或者 []string, [][]string 等，取决于问题的解类型

// backtrack 是回溯函数的核心
// 参数根据具体问题而定，通常包含：
// - currentPath: 当前正在构建的解（路径）
// - choices: 可供选择的元素集合
// - startIndex/index: 当前处理到 choices 的哪个位置
// - ... 其他可能需要的状态信息或约束条件
func backtrack(currentPath []int, choices []int, startIndex int /* ...其他参数 */) {
    // 1. 终止条件 / 找到解的条件
    // 如果 currentPath 满足了问题的解条件，则将其加入 result
    // 注意：需要对 currentPath 进行深拷贝，因为它是共享的，后续会修改
    if isSolution(currentPath /* ... */) {
        temp := make([]int, len(currentPath))
        copy(temp, currentPath)
        result = append(result, temp)
        // 如果只需要一个解，可以在这里 return
        // return
    }

    // 2. 剪枝条件 (可选)
    // 如果当前路径已经不符合约束条件，或者不可能通向有效解，则直接返回
    if shouldPrune(currentPath /* ... */) {
        return
    }

    // 3. 遍历所有可能的选择
    // 通常从 startIndex 开始，避免重复选择（针对组合问题）或已用过的选择
    for i := startIndex; i < len(choices); i++ {
        // 4. 做选择 (做出决策)
        // 将 choices[i] 加入 currentPath
        // 同时更新其他状态，例如标记 choices[i] 为已使用
        currentPath = append(currentPath, choices[i])
        // updateOtherStates(choices[i]) // 例如，N皇后问题中标记行列对角线被占用

        // 5. 递归调用，进入下一层决策
        // startIndex 传入 i+1 通常用于组合问题，确保不重复选择
        // index 传入 i （或者其他形式）用于排列问题，下次从头遍历
        backtrack(currentPath, choices, i+1 /* ... */)

        // 6. 撤销选择 (回溯)
        // 将 choices[i] 从 currentPath 移除
        // 恢复之前更新的其他状态，回到上一个决策点
        currentPath = currentPath[:len(currentPath)-1]
        // revertOtherStates(choices[i])
    }
}

// 辅助函数，判断是否是有效解 (根据具体问题实现)
func isSolution(path []int /* ... */) bool {
    // 示例：如果path的长度达到某个值，则认为是解
    // return len(path) == targetLength
    return false // 占位符
}

// 辅助函数，判断是否需要剪枝 (根据具体问题实现)
func shouldPrune(path []int /* ... */) bool {
    // 示例：如果path的和超过某个值，则剪枝
    // sum := 0
    // for _, v := range path { sum += v }
    // return sum > maxSum
    return false // 占位符
}

注意事项：

  • currentPath 是一个切片，在 Go 中切片是引用类型。在将 currentPath 添加到 result 时，必须进行深拷贝，否则 result 中的所有元素最终都将指向同一个被修改的切片，导致结果不正确。
  • startIndex 的使用在组合问题和排列问题中有所不同。
    • 组合问题：startIndex 通常在递归调用中传递 i+1，以确保每个元素只被考虑一次，并且避免生成重复的组合。
    • 排列问题：通常需要一个布尔数组 used 来标记哪些元素已被使用，每次从 0 到 len(choices)-1 遍历，跳过 used 为 true 的元素。

6. 经典示例

示例1：子集（Subsets）

问题描述：给定一组不含重复元素的整数 nums，返回其所有可能的子集（幂集）。解集不能包含重复的子集。

例如：nums = [1, 2, 3]，返回 [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]。

思路：对于 nums 中的每个元素，我们有两个选择：包含它，或者不包含它。回溯函数需要记录当前考虑的索引 start 和当前构建的子集 currentSubset。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package main

import "fmt"

var subsetsResult [][]int

func subsets(nums []int) [][]int {
    subsetsResult = [][]int{} // 重置全局变量
    backtrackSubsets([]int{}, nums, 0)
    return subsetsResult
}

// backtrackSubsets
// currentSubset: 当前构建的子集
// nums: 原始数组
// startIndex: 当前从 nums 的哪个位置开始考虑
func backtrackSubsets(currentSubset []int, nums []int, startIndex int) {
    // 1. 终止条件 / 找到解的条件
    // 每次递归调用时，currentSubset 都是一个有效的子集，将其加入结果
    temp := make([]int, len(currentSubset))
    copy(temp, currentSubset)
    subsetsResult = append(subsetsResult, temp)

    // 2. 剪枝条件 (这里没有明确的剪枝，因为所有路径都是有效的子集)
    // 但可以理解为：如果 startIndex 已经超出 nums 范围，for 循环自然不会执行，从而终止

    // 3. 遍历所有可能的选择
    // 从 startIndex 开始，避免重复（例如 [1,2] 和 [2,1] 算作同一个子集）
    for i := startIndex; i < len(nums); i++ {
        // 4. 做选择
        currentSubset = append(currentSubset, nums[i])

        // 5. 递归调用，进入下一层决策
        // 下一次从 i+1 开始考虑，确保不会选择重复的元素
        backtrackSubsets(currentSubset, nums, i+1)

        // 6. 撤销选择 (回溯)
        currentSubset = currentSubset[:len(currentSubset)-1]
    }
}

func main() {
    fmt.Println("Subsets for [1, 2, 3]:", subsets([]int{1, 2, 3}))
    // Output: Subsets for [1, 2, 3]: [[], [1], [1 2], [1 2 3], [1 3], [2], [2 3], [3]]
    fmt.Println("Subsets for []:", subsets([]int{}))
    // Output: Subsets for []: [[]]
    fmt.Println("Subsets for [0]:", subsets([]int{0}))
    // Output: Subsets for [0]: [[], [0]]
}

示例2：全排列（Permutations）

问题描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

例如：nums = [1, 2, 3]，返回 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]。

思路：每次选择一个尚未使用的数字添加到当前排列中，直到排列的长度等于 nums 的长度。需要一个布尔数组 used 来跟踪哪些数字已被使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package main

import "fmt"

var permuteResult [][]int

func permute(nums []int) [][]int {
    permuteResult = [][]int{} // 重置全局变量
    used := make([]bool, len(nums)) // 记录元素是否已被使用
    backtrackPermute([]int{}, nums, used)
    return permuteResult
}

// backtrackPermute
// currentPermute: 当前构建的排列
// nums: 原始数组
// used: 记录 nums 中每个元素是否已被使用
func backtrackPermute(currentPermute []int, nums []int, used []bool) {
    // 1. 终止条件 / 找到解的条件
    // 当当前排列的长度等于原始数组的长度时，找到一个有效排列
    if len(currentPermute) == len(nums) {
        temp := make([]int, len(currentPermute))
        copy(temp, currentPermute)
        permuteResult = append(permuteResult, temp)
        return // 找到一个解后，当前分支结束
    }

    // 2. 遍历所有可能的选择
    // 从头开始遍历 nums，因为排列中元素的位置很重要
    for i := 0; i < len(nums); i++ {
        // 3. 剪枝条件
        // 如果 nums[i] 已经被使用过，则跳过
        if used[i] {
            continue
        }

        // 4. 做选择
        currentPermute = append(currentPermute, nums[i])
        used[i] = true // 标记 nums[i] 已被使用

        // 5. 递归调用
        backtrackPermute(currentPermute, nums, used)

        // 6. 撤销选择 (回溯)
        used[i] = false // 恢复 nums[i] 的使用状态
        currentPermute = currentPermute[:len(currentPermute)-1] // 从排列中移除
    }
}

func main() {
    fmt.Println("Permutations for [1, 2, 3]:", permute([]int{1, 2, 3}))
    // Output: Permutations for [1, 2, 3]: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
    fmt.Println("Permutations for [0, 1]:", permute([]int{0, 1}))
    // Output: Permutations for [0, 1]: [[0 1] [1 0]]
}

示例3：N皇后（N-Queens）

问题描述：N皇后问题是在 N×N 的国际象棋棋盘上放置 N 个皇后，使得任何两个皇后都不能互相攻击。一个皇后可以攻击同一行、同一列或同一对角线上的其他皇后。返回所有不同的 N 皇后问题的解决方案。

思路：逐行放置皇后。对于每一行，尝试在所有列中放置皇后。放置前检查该位置是否与已放置的皇后冲突（即是否在同一列或对角线）。如果冲突，则跳过；如果不冲突，则放置皇后并进入下一行。放置后，需要标记该列和两条对角线为已占用。回溯时，撤销标记。

冲突检查： 假设当前在 (row, col) 放置皇后：

  • 同列：检查 col 列是否已有皇后。
  • 主对角线（从左上到右下）：row - col 的值是常数。
  • 副对角线（从右上到左下）：row + col 的值是常数。 为了方便处理，可以维护三个布尔数组：colUsed、diag1Used (主对角线)、diag2Used (副对角线)。 diag1Used 的索引为 row - col + n - 1 （加 n-1 是为了保证索引非负）。 diag2Used 的索引为 row + col。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package main

import "fmt"
import "strings"

var nQueensResult [][]string
var nQueensN int
var colUsed []bool    // 记录列是否被占用
var diag1Used []bool  // 记录主对角线 (row - col) 是否被占用
var diag2Used []bool  // 记录副对角线 (row + col) 是否被占用

func solveNQueens(n int) [][]string {
    nQueensResult = [][]string{} // 重置全局变量
    nQueensN = n
    colUsed = make([]bool, n)
    diag1Used = make([]bool, 2*n-1) // 主对角线有 2*n-1 条
    diag2Used = make([]bool, 2*n-1) // 副对角线有 2*n-1 条

    // 初始化棋盘
    board := make([]string, n)
    for i := 0; i < n; i++ {
        board[i] = strings.Repeat(".", n)
    }

    backtrackNQueens(0, board) // 从第0行开始放置皇后
    return nQueensResult
}

// backtrackNQueens
// row: 当前尝试放置皇后的行
// board: 当前的棋盘状态
func backtrackNQueens(row int, board []string) {
    // 1. 终止条件 / 找到解的条件
    // 如果所有行都已放置皇后，则找到一个解
    if row == nQueensN {
        tempBoard := make([]string, nQueensN)
        copy(tempBoard, board) // 深拷贝棋盘状态
        nQueensResult = append(nQueensResult, tempBoard)
        return
    }

    // 2. 遍历当前行的所有列，尝试放置皇后
    for col := 0; col < nQueensN; col++ {
        // 3. 剪枝条件 (冲突检查)
        // 如果当前位置 (row, col) 所在列、主对角线或副对角线已被占用，则跳过
        if colUsed[col] || diag1Used[row-col+nQueensN-1] || diag2Used[row+col] {
            continue
        }

        // 4. 做选择 (放置皇后)
        // 更新棋盘
        rowChars := []byte(board[row])
        rowChars[col] = 'Q'
        board[row] = string(rowChars)

        // 标记列和对角线为已占用
        colUsed[col] = true
        diag1Used[row-col+nQueensN-1] = true
        diag2Used[row+col] = true

        // 5. 递归调用，进入下一行
        backtrackNQueens(row+1, board)

        // 6. 撤销选择 (回溯)
        // 恢复棋盘
        rowChars[col] = '.'
        board[row] = string(rowChars)

        // 恢复列和对角线的使用状态
        colUsed[col] = false
        diag1Used[row-col+nQueensN-1] = false
        diag2Used[row+col] = false
    }
}

func main() {
    fmt.Println("Solutions for N=4 Queens:")
    solutions4 := solveNQueens(4)
    for _, sol := range solutions4 {
        for _, r := range sol {
            fmt.Println(r)
        }
        fmt.Println()
    }
    // Output will be:
    // .Q..
    // ...Q
    // Q...
    // ..Q.
    //
    // ..Q.
    // Q...
    // ...Q
    // .Q..

    fmt.Println("Solutions for N=1 Queens:")
    solutions1 := solveNQueens(1)
    for _, sol := range solutions1 {
        for _, r := range sol {
            fmt.Println(r)
        }
        fmt.Println()
    }
    // Output:
    // Q
}

7.剪枝去重方式

在回溯算法中，当输入数据包含重复元素时，如果不进行特殊处理，往往会生成重复的结果。去重的目标是确保最终的结果集中不包含相同的组合或排列。

去重策略通常有两种：

  1. **树层去重 (Level-wise Pruning)**：
    • 目标：防止在同一层递归中，因为选择相同的值而产生重复的组合/排列。
    • 何时使用：主要用于组合问题（如子集、组合总和），确保生成的组合是唯一的。它也用于排列问题，避免同一层中选择重复的元素导致重复的排列。
    • 核心思想：在 for 循环遍历选择时，如果当前要选择的元素与同一层中前一个被考虑的元素值相同，并且前一个元素已经被跳过，那么当前元素也跳过。
    • 实现方式：
      • 前提：输入数组必须先排序。
      • 条件：if i > startIndex && nums[i] == nums[i-1] { continue } (对于组合问题)
      • 条件：if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue } (对于排列问题，因为排列不需要index，所有元素都需要拿)
  2. **树枝去重 (Branch-wise Pruning)**：
    • 目标：防止在同一条递归路径上（即，一个正在构建的组合或排列中），重复使用同一个原始索引位置的元素。
    • 何时使用：主要用于全排列问题，因为每个元素（按其原始索引）在一次排列中只能使用一次。
    • 核心思想：维护一个 used 数组（或哈希表）来记录 nums 数组中每个元素是否已经在当前路径上被选中。
    • 实现方式：
      • 条件：if used[i] { continue }

总结区别：

特性 树层去重 (Level-wise Pruning) 树枝去重 (Branch-wise Pruning)
目标 避免在同一层递归中，因选择值相同的元素而产生重复结果 避免在同一条路径上，重复使用同一个原始索引的元素
应用 组合问题 (如 Subsets II, Combination Sum II) 全排列问题 (如 Permutations I、 II)
关键 依靠排序和 if i > startIndex && nums[i] == nums[i-1] 或者`if i > 0 && nums[i] == nums[i-1] && !used[i-1] 依靠 used 数组和 if used[i]
时机 在 for 循环内部，append 之前，基于前一个同层元素 在 for 循环内部，append 之前，基于 used 数组
理解 continue 掉当前 for 循环的 i 次迭代 continue 掉当前 for 循环的 i 次迭代
组合应用 全排列II 中同时需要这两种去重，if i > 0 && nums[i] == nums[i-1] && !used[i-1] 便是树层去重在排列问题中的体现 几乎所有全排列问题都需要树枝去重 (used 数组)

8. 总结

回溯算法是一种强大的暴力搜索技术，尤其适用于解决组合优化问题。它的核心在于“试探”、“探索”、“判断”和“撤销”。理解并掌握回溯算法的通用模板和剪枝技巧，是解决许多复杂算法问题的关键。在Go语言中，需要特别注意切片作为引用类型的特性，在将中间结果添加到最终结果集时进行深拷贝，以避免意外的修改。

#原创 #数据结构 #算法
06.算法——回溯
https://blog.longpi1.com/2025/06/18/06-算法回溯/