回溯 解题模板

适用场景

排列 / 组合 / 子集 / 分割 / 棋盘问题（N皇后/数独）

通用模板

子集 / 组合 / 排列

 
def backtrack(路径, 选择列表):
 
    if 满足结束条件:
 
        result.append(路径[:])  # 深拷贝！
 
        return
 
    for 选择 in 选择列表:
 
        做选择
 
        backtrack(新路径, 新选择列表)
 
        撤销选择
 

三种经典变体

 
# 1. 子集（无重复，每个元素选或不选）
 
def subsets(nums):
 
    res = []
 
    def backtrack(start, path):
 
        res.append(path[:])            # 每个节点都记录
 
        for i in range(start, len(nums)):
 
            path.append(nums[i])
 
            backtrack(i+1, path)       # 不可重复
 
            path.pop()
 
    backtrack(0, [])
 
    return res
 
# 2. 排列（所有顺序）
 
def permute(nums):
 
    res = []
 
    used = [False] * len(nums)
 
    def backtrack(path):
 
        if len(path) == len(nums):
 
            res.append(path[:]); return
 
        for i in range(len(nums)):
 
            if used[i]: continue
 
            used[i] = True
 
            path.append(nums[i])
 
            backtrack(path)
 
            path.pop(); used[i] = False
 
    backtrack([])
 
    return res
 
# 3. 组合（固定长度，不可重复）
 
def combine(n, k):
 
    res = []
 
    def backtrack(start, path):
 
        if len(path) == k:
 
            res.append(path[:]); return
 
        for i in range(start, n+1):
 
            path.append(i)
 
            backtrack(i+1, path)
 
            path.pop()
 
    backtrack(1, [])
 
    return res
 

去重逻辑

 
# 排序后，同层跳过相同值
 
nums.sort()
 
if i > start and nums[i] == nums[i-1]: continue
 

复杂度总结

模式	时间	空间	典型题
子集	O(n×2^n)	O(n)	78、90
组合	O(C(n,k))	O(k)	77、39、40
排列	O(n×n!)	O(n)	46、47
N皇后	O(n!)	O(n²)	51

关键要点

• 路径深拷贝：res.append(path[:]) 不是 path

• 去重口诀：排序 + 同层跳过

• 剪枝：排序后提前终止（组合总和）

• 排列用 used 数组，组合/子集用 start 索引

→ 查看该分类题目：LeetCode学习路线图 > 十、回溯

---

相似题对比

易混题对	关键区别	解法差异
78子集 vs 90子集II	无重复 vs 有重复	90需排序+同层跳过
46全排列 vs 47全排列II	无重复 vs 有重复	47需 used[i-1]==False 判断
39组合总和 vs 40组合总和II	可重复选 vs 不可重复	39 backtrack(i) vs 40 backtrack(i+1)
77组合 vs 78子集	固定长度 vs 所有长度	组合 path长度==k 才记录；子集每步都记录
79单词搜索 vs 51N皇后	二维网格DFS vs 逐行放置	搜索方向不同

---

测试用例模板

 
# 基础功能
 
assert sorted(subsets([1,2,3])) == sorted([(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)])
 
# 边界
 
assert subsets([]) == [[]]               # 空集
 
assert subsets([1]) == [[], [1]]         # 单元素
 
# 输入约束
 
assert combine(4, 2) == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
 

---

关联题型

关联题型	常见结合方式	典型题目
二叉树	回溯 = 多叉树DFS	46全排列, 77组合
动态规划	回溯 → DP 剪枝优化	39组合总和, 322零钱兑换
图论	回溯在图中的DFS应用	79单词搜索, 200岛屿数量