回溯模板

一句话说明

回溯的骨架永远是三步：做选择、递归下一层、撤销选择。

先抓住它和 DFS 的关系

回溯本质上就是带“撤销动作”的 DFS。
普通 DFS 更像遍历，回溯更像枚举决策树。

所以题目一旦出现：

• 所有方案
• 所有排列
• 所有组合
• 能不能拼出来

基本就要往回溯想。

通用骨架

for 枚举所有可选项:
    做选择
    递归
    撤销选择

这三步少任何一步都不对。

Go 模板：子集

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

Go 模板：去重组合

func CombinationSumUnique(nums []int, target int) [][]int {
    sort.Ints(nums)
 
    result := [][]int{}
    path := []int{}
 
    var backtrack func(start, remain int)
    backtrack = func(start, remain int) {
        if remain == 0 {
            snapshot := append([]int(nil), path...)
            result = append(result, snapshot)
            return
        }
 
        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            if nums[i] > remain {
                break
            }
 
            path = append(path, nums[i])
            backtrack(i+1, remain-nums[i])
            path = path[:len(path)-1]
        }
    }
 
    backtrack(0, target)
    return result
}

什么时候要剪枝

剪枝的本质是：

这条分支已经不可能产生合法答案了

比如：

• 当前和已经超过目标
• 剩余字符数量不够
• 当前状态和前面完全重复

剪枝不是附加技巧，而是回溯能过题的关键之一。

去重最常见的坑

这一句很关键：

if i > start && nums[i] == nums[i-1] { continue }

它表达的是：

• 只跳过同一层的重复选择
• 不是把后面所有相同值都永久禁掉

易错点

回溯模板最容易错的地方

• 保存结果时必须复制当前路径，不能直接存引用。
• 每次 append 后必须有对应的撤销。
• 去重通常是“同层去重”，不是“全局去重”。
• 剪枝条件放早一点，复杂度差很多。

相关主题

• 回溯框架
• DFS模板

---

返回：算法模板