Python 算法基础篇之回溯

1. 回溯算法是什么？

1.1 生活中的回溯

想象你在走迷宫：

• 走到一个岔路口，选择一条路走
• 发现是死胡同，退回岔路口
• 尝试另一条路
• 直到找到出口

这就是回溯：走不通就回头，尝试其他可能。

1.2 算法的定义

回溯算法（Backtracking）：一种通过深度优先搜索遍历解空间树，并在搜索过程中剪枝（排除不可能的分支），从而找到所有（或最优）解的算法技术。

核心特征：

• 系统性：按一定顺序遍历所有可能
• 跳跃性：发现不满足条件时，立即回溯（剪枝）
• 通用性：框架固定，适用于多种组合问题

1.3 回溯 vs 递归 vs DFS

💡一句话：回溯是用递归实现的 DFS，加上剪枝优化。

2. 回溯算法的核心框架

2.1 三大要素

回溯算法必须明确定义以下三个要素：

┌─────────────────────────────────────────┐ │ 路径（Path） │ │ 已经做出的选择，记录当前状态 │ ├─────────────────────────────────────────┤ │ 选择列表（Choices） │ │ 当前可以做的选择 │ ├─────────────────────────────────────────┤ │ 结束条件（Termination） │ │ 到达终止状态，保存结果 │ └─────────────────────────────────────────┘

2.2 通用代码框架

defbacktrack(路径,选择列表):if满足结束条件:结果.append(路径[:])# 注意拷贝！returnfor选择in选择列表:if不满足约束条件:# 剪枝continue做选择# 修改路径backtrack(新路径,新选择列表)# 递归撤销选择# 恢复路径（回溯）

2.3 关键理解：为什么需要"撤销选择"？

# 错误示范：不撤销选择defwrong_backtrack(path,nums):iflen(path)==len(nums):result.append(path)# 保存引用，后续会被修改！returnfornuminnums:ifnuminpath:continuepath.append(num)# 做选择wrong_backtrack(path,nums)# 忘记撤销！path 一直增长# 正确示范：撤销选择defcorrect_backtrack(path,nums):iflen(path)==len(nums):result.append(path[:])# 保存拷贝returnfornuminnums:ifnuminpath:continuepath.append(num)# 做选择correct_backtrack(path,nums)path.pop()# 撤销选择！恢复状态

🎯核心原则：回溯算法的状态共享特性要求，进入递归前修改状态，递归返回后必须恢复状态，保证同一层循环中各选择之间的独立性。

3. 经典例题一：组合问题

3.1 题目描述

从[1, 2, ..., n]中选取k个数，返回所有可能的组合。

示例：n = 4, k = 2
输出：[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

3.2 解题思路

解空间树（n=4, k=2）： 开始 / | | \ 1 2 3 4 /| | | 2 3 4 3 4 / | 3 4 4 有效路径：[1,2] [1,3] [1,4] [2,3] [2,4] [3,4] 剪枝：[2,1] 无效（顺序保证不重复） [3,1] [3,2] 同理

关键设计：

• 避免重复：每次从start开始，不回头选
• 结束条件：len(path) == k

3.3 代码实现

defcombine(n:int,k:int)->list[list[int]]:""" 从 1~n 中选 k 个数的所有组合 时间复杂度：O(C(n,k))，组合数 空间复杂度：O(k)，递归栈深度 """result=[]path=[]defbacktrack(start:int):# 结束条件：已选够 k 个数iflen(path)==k:result.append(path[:])# 保存拷贝return# 选择列表：从 start 开始，避免重复foriinrange(start,n+1):path.append(i)# 做选择backtrack(i+1)# 递归，下次从 i+1 开始path.pop()# 撤销选择backtrack(1)returnresult# 测试print(combine(4,2))# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

3.4 执行过程可视化

backtrack(1): path=[1] ├── backtrack(2): │ path=[1,2] → 长度=2，保存 [1,2] │ path.pop() → [1] ├── backtrack(3): │ path=[1,3] → 保存 [1,3] │ path.pop() → [1] ├── backtrack(4): │ path=[1,4] → 保存 [1,4] │ path.pop() → [1] path.pop() → [] ├── backtrack(2): │ path=[2] │ ├── backtrack(3): │ │ path=[2,3] → 保存 [2,3] │ │ path.pop() → [2] │ ├── backtrack(4): │ │ path=[2,4] → 保存 [2,4] │ │ path.pop() → [2] │ path.pop() → [] └── ... 继续

4. 经典例题二：全排列问题

4.1 题目描述

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

示例：nums = [1, 2, 3]
输出：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

4.2 解题思路

解空间树（nums=[1,2,3]）： 开始 / | \ 1 2 3 / \ / \ / \ 2 3 1 3 1 2 | | | | | | 3 2 3 1 2 1 路径：[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

关键设计：

• 避免重复：用used数组标记已选元素
• 结束条件：len(path) == len(nums)

4.3 代码实现

defpermute(nums:list[int])->list[list[int]]:""" 返回数组的所有全排列 时间复杂度：O(n!)，n 个元素的全排列数 空间复杂度：O(n)，递归栈 + used 数组 """result=[]path=[]used=[False]*len(nums)# 标记数组defbacktrack():# 结束条件：所有元素都已使用iflen(path)==len(nums):result.append(path[:])return# 选择列表：所有未使用的元素foriinrange(len(nums)):ifused[i]:# 剪枝：已使用则跳过continue# 做选择used[i]=Truepath.append(nums[i])# 递归backtrack()# 撤销选择path.pop()used[i]=Falsebacktrack()returnresult# 测试print(permute([1,2,3]))# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

4.4 与组合问题的区别

5. 经典例题三：N 皇后问题

5.1 题目描述

在n × n的棋盘上放置n个皇后，使其不能互相攻击（任意两个皇后不在同一行、同一列、同一对角线）。

示例：n = 4
输出：2 种解法

解法1: 解法2: . Q . . . . Q . . . . Q Q . . . Q . . . . . . Q . . Q . . Q . .

5.2 解题思路

关键观察：

• 每行必须且只能放一个皇后（否则同行冲突）
• 用board[i] = j表示第i行第j列放皇后

冲突检测：

• 同列：board[i] == board[row]
• 对角线：abs(board[i] - board[row]) == abs(i - row)

5.3 代码实现

defsolve_n_queens(n:int)->list[list[str]]:""" N 皇后问题：返回所有解法 时间复杂度：O(n!)，实际因剪枝远小于此 空间复杂度：O(n)，递归栈 """result=[]board=[-1]*n# board[i] = 第i行皇后所在的列defis_valid(row:int,col:int)->bool:"""检查在 (row, col) 放皇后是否合法"""foriinrange(row):# 同列 或 同对角线ifboard[i]==colorabs(board[i]-col)==abs(i-row):returnFalsereturnTruedefbacktrack(row:int):# 结束条件：所有行都放置成功ifrow==n:# 生成棋盘表示solution=[]forcolinboard:line="."*col+"Q"+"."*(n-col-1)solution.append(line)result.append(solution)return# 选择列表：当前行的每一列forcolinrange(n):ifnotis_valid(row,col):# 剪枝：冲突位置跳过continueboard[row]=col# 做选择backtrack(row+1)# 递归：处理下一行board[row]=-1# 撤销选择（回溯）backtrack(0)returnresult# 测试solutions=solve_n_queens(4)print(f"4 皇后问题共有{len(solutions)}种解法：\n")fori,solinenumerate(solutions,1):print(f"解法{i}:")forlineinsol:print(line)print()

输出：

4 皇后问题共有 2 种解法： 解法 1: .Q.. ...Q Q... ..Q. 解法 2: ..Q. Q... ...Q .Q..

5.4 解的数量规律

6. 经典例题四：子集问题

6.1 题目描述

给定一个不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。

示例：nums = [1, 2, 3]
输出：[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

6.2 解题思路

关键洞察：每个元素有两种选择——选或不选

解空间树（nums=[1,2,3]）： 开始 / \ 选1 不选1 / \ / \ 选2 不选2 选2 不选2 / \ / \ / \ / \ 选3 ...（共8个叶子节点） 路径：[] [3] [2] [2,3] [1] [1,3] [1,2] [1,2,3]

6.3 代码实现

defsubsets(nums:list[int])->list[list[int]]:""" 返回数组的所有子集（幂集） 时间复杂度：O(2^n)，每个元素选/不选两种状态 空间复杂度：O(n)，递归栈深度 """result=[]path=[]defbacktrack(start:int):# 关键：每个节点都是一个有效子集！result.append(path[:])# 选择列表：从 start 开始的每个元素foriinrange(start,len(nums)):path.append(nums[i])# 做选择：选 nums[i]backtrack(i+1)# 递归path.pop()# 撤销选择：不选 nums[i]backtrack(0)returnresult# 测试print(subsets([1,2,3]))# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

6.4 另一种思路：逐个元素选/不选

defsubsets_binary(nums:list[int])->list[list[int]]:""" 用二进制表示选/不选：000 ~ 111 第 i 位为 1 表示选 nums[i] """n=len(nums)result=[]# 枚举 0 到 2^n - 1formaskinrange(1<<n):# 1 << n = 2^nsubset=[]foriinrange(n):ifmask&(1<<i):# 第 i 位是否为 1subset.append(nums[i])result.append(subset)returnresult# 测试print(subsets_binary([1,2,3]))

7. 剪枝优化：让回溯更高效

7.1 什么是剪枝？

剪枝（Pruning）：在搜索过程中，提前判断某条路径不可能产生有效解，从而跳过该分支，减少搜索空间。

无剪枝：遍历整棵树 〇 /|\ 〇 〇 〇 /|\ ... 〇 〇 〇 有剪枝：剪掉无效分支 〇 /| 〇 〇 ✂️ /| 〇 〇

7.2 剪枝策略

策略1：约束剪枝（可行性剪枝）

# 组合问题优化：剩余元素不够选时直接返回defcombine_optimized(n:int,k:int)->list[list[int]]:result=[]path=[]defbacktrack(start:int):iflen(path)==k:result.append(path[:])return# 剪枝：剩余元素不足以凑够 k 个# 还需要选：need = k - len(path)# 可选范围：[start, n]，共 n - start + 1 个# 如果 n - start + 1 < need，直接返回need=k-len(path)ifn-start+1<need:returnforiinrange(start,n+1):path.append(i)backtrack(i+1)path.pop()backtrack(1)returnresult

策略2：排序剪枝（常用于求和类问题）

defcombination_sum(candidates:list[int],target:int)->list[list[int]]:""" 组合总和： candidates 中数字无限制重复选取，和为 target 的所有组合 """candidates.sort()# 排序，便于剪枝result=[]path=[]defbacktrack(start:int,remain:int):ifremain==0:result.append(path[:])returnifremain<0:# 剪枝：和已超过 targetreturnforiinrange(start,len(candidates)):# 剪枝：当前数已大于剩余值，后面更大，直接breakifcandidates[i]>remain:breakpath.append(candidates[i])backtrack(i,remain-candidates[i])# i 可重复选path.pop()backtrack(0,target)returnresult# 测试print(combination_sum([2,3,6,7],7))# [[2, 2, 3], [7]]

策略3：记忆化剪枝（去重）

defpermute_unique(nums:list[int])->list[list[int]]:""" 全排列 II：数组可能包含重复数字 """nums.sort()# 排序，让重复数字相邻result=[]path=[]used=[False]*len(nums)defbacktrack():iflen(path)==len(nums):result.append(path[:])returnforiinrange(len(nums)):ifused[i]:continue# 剪枝：跳过同一层中的重复数字# 条件：当前数字等于前一个，且前一个未使用（说明是同层）ifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack()path.pop()used[i]=Falsebacktrack()returnresult# 测试print(permute_unique([1,1,2]))# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

8. 回溯算法的复杂度分析

8.1 时间复杂度

回溯算法的时间复杂度取决于解空间树的大小：

8.2 空间复杂度

• 递归栈深度：通常为 O(n)
• 路径存储：通常为 O(n)
• 总空间：O(n) 或 O(n²)（保存所有解时）

8.3 优化效果对比

以组合问题combine(20, 10)为例：

以combination_sum([2,3,5], 8)为例：

9. 总结与思维导图

9.1 回溯算法核心框架

defbacktrack(路径,选择列表):if满足结束条件:result.append(路径[:])returnfor选择in选择列表:if不满足约束:# 剪枝continue做选择 backtrack(新路径,新选择列表)撤销选择# 关键！

9.2 问题类型速查

9.3 回溯算法的优缺点