回溯框架

一句话说明

回溯就是在决策树上做 DFS，只不过每走一步都要记得：递归回来后把这一步撤销掉。

先把回溯看成决策树

以 [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]

你每往下一层，就是“做一个选择”；
你从递归返回，就是“撤销刚才那次选择”。

Go 模板

这是最通用的回溯骨架：

func backtrack(path *[]int, choices []int, used []bool, result *[][]int) {
    if endCondition(*path) {
        snapshot := append([]int(nil), (*path)...)
        *result = append(*result, snapshot)
        return
    }
 
    for i, choice := range choices {
        if used[i] {
            continue
        }
 
        // 做选择
        *path = append(*path, choice)
        used[i] = true
 
        // 递归
        backtrack(path, choices, used, result)
 
        // 撤销选择
        used[i] = false
        *path = (*path)[:len(*path)-1]
    }
}

回溯三问

每道题都先回答这三个问题：

1. 路径是什么？
2. 当前可选项有哪些？
3. 什么时候算一个完整解？

很多题只要这三件事想明白，代码自然就出来了。

排列问题

特点：

• 顺序重要
• 每个元素通常只能用一次
• 常配合 used 数组

func permute(nums []int) [][]int {
    result := make([][]int, 0)
    path := make([]int, 0, len(nums))
    used := make([]bool, len(nums))
 
    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            snapshot := append([]int(nil), path...)
            result = append(result, snapshot)
            return
        }
 
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
 
            path = append(path, nums[i])
            used[i] = true
            dfs()
            used[i] = false
            path = path[:len(path)-1]
        }
    }
 
    dfs()
    return result
}

组合问题

特点：

• 顺序不重要
• 为了避免重复，下一层从 start 之后继续选

func combine(n, k int) [][]int {
    result := make([][]int, 0)
    path := make([]int, 0, k)
 
    var dfs func(start int)
    dfs = func(start int) {
        if len(path) == k {
            snapshot := append([]int(nil), path...)
            result = append(result, snapshot)
            return
        }
 
        for i := start; i <= n; i++ {
            path = append(path, i)
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
 
    dfs(1)
    return result
}

子集问题

特点：

• 每个元素本质上都是“选 / 不选”
• 每个中间节点本身就是一个答案

func subsets(nums []int) [][]int {
    result := make([][]int, 0)
    path := make([]int, 0)
 
    var dfs func(start int)
    dfs = func(start int) {
        snapshot := append([]int(nil), path...)
        result = append(result, snapshot)
 
        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
 
    dfs(0)
    return result
}

去重怎么做

子集 / 组合去重

思路是：

• 先排序
• 同一层遇到相同数字时，只用第一个

func subsetsWithDup(nums []int) [][]int {
    slices.Sort(nums)
    result := make([][]int, 0)
    path := make([]int, 0)
 
    var dfs func(start int)
    dfs = func(start int) {
        snapshot := append([]int(nil), path...)
        result = append(result, snapshot)
 
        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] {
                continue
            }
 
            path = append(path, nums[i])
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
 
    dfs(0)
    return result
}

排列去重

排列去重更容易错，因为“同层去重”和“同枝去重”不是一回事。

func permuteUnique(nums []int) [][]int {
    slices.Sort(nums)
    result := make([][]int, 0)
    path := make([]int, 0, len(nums))
    used := make([]bool, len(nums))
 
    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            snapshot := append([]int(nil), path...)
            result = append(result, snapshot)
            return
        }
 
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
 
            // 同一层中，相同元素只用第一个
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
 
            path = append(path, nums[i])
            used[i] = true
            dfs()
            used[i] = false
            path = path[:len(path)-1]
        }
    }
 
    dfs()
    return result
}

剪枝怎么想

回溯真正的难点往往不是“会不会写模板”，而是“能不能早点停”。

超目标值直接停

func combinationSum(candidates []int, target int) [][]int {
    slices.Sort(candidates)
    result := make([][]int, 0)
    path := make([]int, 0)
 
    var dfs func(start, sum int)
    dfs = func(start, sum int) {
        if sum == target {
            snapshot := append([]int(nil), path...)
            result = append(result, snapshot)
            return
        }
        if sum > target {
            return
        }
 
        for i := start; i < len(candidates); i++ {
            if sum+candidates[i] > target {
                break
            }
 
            path = append(path, candidates[i])
            dfs(i, sum+candidates[i])
            path = path[:len(path)-1]
        }
    }
 
    dfs(0, 0)
    return result
}

排序后，sum + candidates[i] > target 时直接 break，因为后面的数只会更大。

回溯和 DFS 的关系

回溯 = DFS + 做选择 + 撤销选择

普通 DFS 更像“遍历”：

• 找连通块
• 走路径
• 判断可达性

回溯更像“枚举所有方案”：

• 排列
• 组合
• 子集
• N 皇后

易错点

• result 里保存路径时一定要复制，不能直接塞当前切片。
• 撤销选择必须和做选择严格成对出现。
• 去重条件要分清“同层”还是“同枝”。
• 组合题常用 start，排列题常用 used，别混。

相关主题

• 全排列问题
• 组合总和问题
• N皇后问题

---

返回：搜索算法