Python递归求解排列组合：剪枝、去重与迭代化工程实践

Python求解排列组合，这个话题写到第四篇，基本进入了递归程序设计艺术里最见功底的部分：剪枝、去重和工程化改造。前面几篇已经把递归树怎么画、全排列和组合的基础回溯怎么写讲透了，但很多朋友会在真实场景里碰壁：数据稍微大一点，程序就跑不动；输入里有重复元素，结果重复得没法看；想处理带约束条件的搜索，又不知道怎么把限制加到递归里。这篇就是来填这些坑的，适合已经写过基础递归回溯、想进一步提升的人。读完你至少能收获三样东西：一套可复用的剪枝思路、一个处理重复元素的去重模板，以及把递归改造成生成器或迭代算法的具体方法。

1. 递归求解排列组合的整体思路与系列衔接

1.1 从选择树理解排列与组合的区别

先回顾一下两种最基本形态。排列关心顺序，所以递归时每次都在“所有元素”里挑一个放进当前位置，用一个used数组标记谁用过；组合不关心顺序，所以递归时用start规定“接下来只能从start及之后选”，避免同一组合被不同顺序重复生成。这两个起点看起来差不多，后续的剪枝和去重策略却完全不一样，理解错位就会踩坑。

def permute(nums): res = [] used = [False] * len(nums) def dfs(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]) dfs(path) path.pop() used[i] = False dfs([]) return res def combine(n, k): res = [] def dfs(start, path): if len(path) == k: res.append(path[:]) return for i in range(start, n + 1): path.append(i) dfs(i + 1, path) path.pop() dfs(1, []) return res

排列的递归树是一棵多叉树：第一层有n个分支，第二层每个分支又有n-1个分支，直到选满。组合的递归树更像一个不断收缩的三角形：每次进入下一层，可选起点都往后移一位。两个模板都短，但真正难的不是模板本身，而是怎么在模板里加入“业务规则”。

1.2 第4篇要解决的三个核心痛点

说白了，前几篇能让程序跑出正确答案，这篇要让程序在正确答案的路上跑得又快又稳。第一个痛点是状态爆炸：全排列的规模是n!，哪怕n=10也有 3628800 条路径；组合稍微好一点，但C(20,10)=184756也够呛。关键是每个叶子节点还有一次列表拷贝，最终把结果存进res时，内存和时间都会成倍增长。

第二个痛点是重复元素：如果输入是[1,1,2]，按索引生成的全排列是 6 条，但按值去重后只有[1,1,2]、[1,2,1]、[2,1,1]三种。业务上如果只关心值，不关心元素位置，那重复分支就不是“可以接受”，而是“必须干掉”。

第三个痛点是工程性能：Python 的递归不是免费的，函数调用开销、列表拷贝、全局结果列表都会拖慢程序。再加上有些场景根本不需要一次拿到全部结果，而需要边生成边消费。这三个痛点正好对应后面章节的剪枝、去重和迭代化改造。

2. 剪枝：让递归少走无效分支

2.1 剪枝的本质是提前说“不”

剪枝这个词很形象。想象一个人走迷宫，走到一个岔路口，发现前面已经是一堵墙，正常人不会继续走进去撞墙，而是直接退回上一个路口选别的方向。递归里的剪枝也一样：在进入下一层之前，判断当前分支到底有没有可能通向合法结果。如果不可能，就直接return或者continue，不进去。

剪枝有一个重要原则：宁可多保留一个分支，也不要漏掉一个解。剪枝条件是“充分必要”的逻辑，必须是数学上站得住脚的。比如“剩余可选数量不足一定凑不齐 k 个”，这是必然的，剪掉不会影响结果；但如果你用一个“当前和已经大于目标就不继续”的条件去处理负数数组，就会漏掉后续负数把和拉回来的情况。所以每次写剪枝前，都要先问自己：这个条件在什么情况下会误伤合法解？

2.2 从组合求和中看排序剪枝的落点

一个非常典型的案例是“组合总和 II”：给定一个数组nums和一个目标值target，找出所有和为target的组合，数组里每个元素只能使用一次，并且结果里不能有重复组合。这个题把排序、去重、剪枝全串起来了。

def combination_sum2(nums, target): nums.sort() res = [] path = [] def dfs(start, remain): if remain == 0: res.append(path[:]) return if start >= len(nums) or nums[start] > remain: return for i in range(start, len(nums)): if nums[i] > remain: break if i > start and nums[i] == nums[i - 1]: continue path.append(nums[i]) dfs(i + 1, remain - nums[i]) path.pop() dfs(0, target) return res

这里的剪枝有两层。第一层在函数入口：如果剩余部分最小的nums[start]都已经大于remain，说明后面所有元素都大于剩余目标，继续递归没有任何意义。第二层在for循环里：一旦nums[i] > remain，直接break，因为数组已经排序，后面的数只会更大，不可能再满足要求。很多新手会写成continue，结果只是跳过当前元素，后面还继续遍历更大的数，白白浪费。

至于if i > start and nums[i] == nums[i - 1]的去重逻辑，后面专门展开，这里先不细说。观察整个函数可以发现，剪枝不是最后加上的“装饰”，而是从排序开始就已经在为剪枝布局了。

2.3 通用剩余数量剪枝：写给组合生成

在纯组合生成中，有个几乎万能的小剪枝：当前已经选了len(path)个元素，还从i继续往后挑，最多还能挑n - i + 1个，如果两者相加都不够k，那这层循环再往后也不可能凑齐k个。

def combine_k(n, k): res = [] def dfs(start, path): if len(path) == k: res.append(path[:]) return for i in range(start, n + 1): if len(path) + (n - i + 1) < k: break path.append(i) dfs(i + 1, path) path.pop() dfs(1, []) return res

这条剪枝不改变任何结果，只是把“必死”的子树提前砍掉。比如n=20, k=10，当start已经走到 15 的时候，就算把后面所有元素全选上也不够 10 个，直接跳出循环。别小看这一步，它能砍掉递归树里大量靠近根部的无效分支，让程序从“勉强能跑”变成“轻松秒开”。

2.4 剪枝也分层次，别做无用功

剪枝放哪里也是有讲究的。凡是与当前循环变量无关的全局性判断，尽量放在递归函数开头，例如“当前学分已经超过上限”“剩余元素总数不足”。凡是只影响当前某个具体选择的判断，放在for循环里，例如“当前元素大于剩余目标”。

我见过有人把所有剪枝都堆在函数开头，结果某些循环内本来可以直接 break 的分支，也被层层调用后才意识到不行，白白多了许多递归调用。反过来，也有人把全局判断写在循环里，每选一个元素就重复算一次，多了很多不必要的开销。剪枝本身是有成本的，一个O(1)判断能跳过一个指数级子树，当然值得；但如果这个判断本身要扫描整个列表、计算一个昂贵的统计值，那就要想想是不是该把结果缓存起来。

3. 去重：让相同输入不产生重复结果

3.1 重复来自下标，而不是值

输入[1,1,2]时，递归会把两个 1 当成两个不同的元素，因为它们的下标不同。于是生成的全排列里，第一个 1 在前的方案和第二个 1 在前的方案，在业务上完全一样，却会被当成两条结果输出。这就是重复问题的根源：我们用下标区分元素，但业务里只看值。

去重的本质是：在同一个递归层，如果两个起点位置上的值相同，那后面展开的子树必然相同，只需要保留第一个，跳过其余。这句话理解透了，全排列和组合的去重都能顺下来。

3.2 全排列去重：used 数组的两种姿势

全排列去重最常见的写法是先排序，然后在for循环里加一句判断。排序的目的是让相同元素相邻，这样判断“前一个值相同”只要看nums[i-1]就行。

def permute_unique(nums): nums.sort() res = [] used = [False] * len(nums) def dfs(path): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True path.append(nums[i]) dfs(path) path.pop() used[i] = False dfs([]) return res

关于not used[i-1]这个条件，网上有很多说法。我建议这样理解：当递归进入某一层，正在决定“这一层的开头放哪个元素”时，如果前一个相同元素在当前层还没有被使用，说明这个相同值已经在前面某个分支被当作本层起点处理过了，当前分支就是重复分支，必须跳过。反过来，如果前一个相同元素已经被使用，说明它在上层路径里已经占了一个位置，当前元素可以作为后续位置继续放，这是合法的不同路径。

也有人用used[i-1]作为条件，效果同样是去重，但生成结果的顺序会不同。两种写法没有绝对对错，关键是你得清楚自己的状态语义，别把两种写法混着抄，抄着抄着就把合法结果也跳过了。

3.3 组合去重：排序加起点判断

组合去重比排列简单，因为组合搜索不回头。组合递归里的start参数保证了每条路径的下标严格递增，所以重复只可能发生在“同一层循环里，相同值被选了两个位置”。解决办法就是排序后，在循环里遇到i > start且nums[i] == nums[i-1]时跳过。

if i > start and nums[i] == nums[i - 1]: continue

这个条件在之前的组合求和中已经出现过。理解它只需要抓住一点：当i == start时，这个值是本层第一个被考虑的起点，需要正常处理；当i > start时，说明这个值作为起点已经在前面某个分支处理过了，如果值相同，后面展开产生的组合必然一样，直接continue。

3.4 用 set 兜底，但别当常规武器

很多人在递归里不想动脑筋，直接在收集结果时加一个seen集合，遇到没见过的tuple(path)才加入res。这个方法代码很短，效果也直接，但代价是：所有重复分支在递归层仍然会完整生成一遍，只是到最后被过滤掉了。也就是说，你省的是“存储结果”的力气，但一点没省“搜索路径”的力气。

我在实践中只把set用来做小规模验证，或者用来和递归剪枝的结果互相对拍。比如写了一个复杂的剪枝版本，拿它在[1,1,2,3,4]这种小数据上和暴力set版本对比，确认结果集合一致，再放心上线。一旦数据量上来，还是得靠递归内部的去重把重复分支提前砍掉，这才是治本。

4. 从递归到迭代：工程里的性能优化

4.1 递归的隐形开销

Python 的递归调用开销主要来自函数栈帧、参数传递和返回值组装。一个递归函数执行几十万次调用，哪怕每次只做一点点事，累积起来也很可观。更麻烦的是，Python 对递归深度有默认限制，通常是 1000。排列组合问题的调用链深度一般不会太深，比如 10 个元素的全排列，递归深度是 10，根本不触碰深度限制；问题在于“调用次数”是整棵递归树的节点数，可能上千万，这才是性能瓶颈。

所以看到RecursionError时，别急着sys.setrecursionlimit(10000)。如果问题出在调用次数太多，把递归上限调到十万也没用，只是把错误往后推。你需要做的是砍分支、加剪枝，或者干脆换成迭代算法。真的需要调大递归深度时，也要小心：C 栈并不因为 Python 设置了上限就无限增长，调得太大可能直接把进程搞崩。

4.2 生成器化：用 yield 以流式方式返回结果

如果结果规模很大，但调用方并不需要一次性拿到全部列表，就可以把递归函数改成生成器。生成器的好处是惰性求值，每yield一次，调用方消费一个，内存里永远只有当前路径。

def permute_gen(nums, path=None, used=None): nums = sorted(nums) n = len(nums) if path is None: path = [] used = [False] * n if len(path) == n: yield tuple(path) return for i in range(n): if used[i]: continue if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True path.append(nums[i]) yield from permute_gen(nums, path, used) path.pop() used[i] = False

调用方可以这样用：

for seq in permute_gen([1, 1, 2]): print(seq)

这里要注意一个细节：path和used不能写成默认参数为可变对象，否则多次调用这个生成器时会共用同一个列表，出现奇怪的结果。所以我用None作为占位，进入函数后再初始化。另外，yield from需要 Python 3.3 以上，现在基本不用担心版本问题。

还有一个很实用的点：因为生成器是惰性的，调用方如果提前break，生成器会被垃圾回收，不会继续跑完剩下所有递归。这在“找到一个可行方案就停止”的搜索场景里非常有用。

4.3 用标准库还是自造轮子

如果只是生成无额外约束的全排列或组合，优先用itertools.permutations和itertools.combinations。它们是 C 语言实现的，性能比自写递归快一个数量级，而且经过了充分测试，边界情况处理得也好。

from itertools import permutations, combinations list(permutations([1, 2, 3], 2)) list(combinations([1, 2, 3], 2))

真正需要自造轮子的场景，永远是“有额外约束”。比如需要剪枝、需要去重、需要把业务规则嵌进搜索过程，这时候标准库帮不上忙，因为标准库不知道你的“先修课”是什么。所以我的建议是：不排斥标准库，但也不要迷信标准库；先看看业务里有没有定制逻辑，有就自己写回溯，没有就直接调库。

4.4 决策对照表

4.5 位掩码生成组合补充

位掩码适合在n很小的场景里快速验证思路。用一个整数 mask 表示哪些元素被选中，1 表示选，0 表示不选，遍历所有 mask，统计二进制中 1 的个数等于k的就是一个组合。

def combine_by_mask(nums, k): n = len(nums) res = [] for mask in range(1 << n): if bin(mask).count("1") == k: res.append([nums[i] for i in range(n) if mask & (1 << i)]) return res

这个方法的复杂度是O(2^n)，n=20时大约 100 万次枚举，勉强能跑；n=30就是 10 亿次，完全不可行。所以位掩码只适合小规模和验证用，真正的生产场景还得靠带剪枝的递归。

5. 常见问题与排查技巧实录

5.1 RecursionError：不是所有问题都该调递归深度

碰到RecursionError: maximum recursion depth exceeded，第一反应不是改限制，而是先看路径有没有在前进。打印一下每次递归进入时的path，如果同一个path反复出现，说明递归没有往终止条件推进，多半是某个状态在递归后又恢复原样，形成了死循环。确认是正常深搜后，再考虑是不是默认深度不够。组合问题里递归深度最多等于k，一般到不了 1000；真到了，建议改成迭代。

python -m cProfile your_script.py

在命令行里跑一下，能立刻看到哪些函数调用次数最多、累计耗时最长。我遇到过一种情况，递归本身只占 20% 的时间，但每个叶子节点都在做一次res.append(path[:])，这个拷贝成了大头。解决办法是把path换成元组，或者用更紧凑的位掩码表示路径。

5.2 结果重复或缺少：先检查去重条件和剪枝边界

去重出问题时，先拿一组小数据验证。全排列用[1,1,2]，预期结果是[1,1,2]、[1,2,1]、[2,1,1]三种；组合用[1,1,2]选 2 个，预期是[1,1]、[1,2]两种。如果结果多了，大概率是去重条件没写对；如果结果少了，可能是剪枝条件把合法分支也砍了。

一个小技巧：先注释掉所有去重和剪枝，跑小数据得到“原始结果”，再用set去重得到“期望结果集”，最后打开剪枝跑一遍，和期望结果集对比。这样能快速定位是剪枝的锅还是去重的锅。

5.3 定位性能瓶颈：别靠猜，用数据说话

我见过不少人凭感觉优化，结果把函数改得面目全非，性能一点没提升。更靠谱的方式是先用timeit测整体耗时，再用cProfile看函数调用分布。最耗时的往往不是递归本身，而是某个O(n)的判断反复执行，或者path[:]拷贝次数太多。

import cProfile cProfile.run("permute_unique([1, 1, 2, 3, 4, 5, 6])")

看输出的时候，注意tottime和cumtime。tottime高表示这个函数自身的运算重，cumtime高表示它内部还调了别的耗时代码。如果问题出在某个 for 循环里的条件判断，可以尝试把判断提前；如果问题出在拷贝，可以看看能不能用不可变对象代替列表。

5.4 测试边界与验证模板

测试时不要只测一个 happy path，至少要覆盖空输入、全重复、k 等于 n、k 等于 0 这几个边界。排列组合的递归很容易在空集合上出问题，比如空列表加path[:]会得到[]，但模板里可能因为len(path)==k而从来不触发。

6. 实战：带先修约束的课程选择

6.1 问题抽象

某课程选择系统里有个小功能：从 6 门课中选 3 门，每门课有学分和先修课要求，选出的组合总学分不能低于 8，先修课必须已经选上。课程信息用一个元组表示：(课程编号, 学分, 先修课编号集合)。为了保证组合搜索能直接使用start递增的模型，课程列表已经按拓扑序排好，先修课编号一定小于后续课程的编号。

这个问题天然适合递归回溯：组合的“选 3 门”是组合问题，先修约束和学分条件是业务剪枝，课程编号唯一决定了不存在同值去重问题，但剪枝策略完全是前面几节的复用。

6.2 实现代码

from typing import List, Tuple, Set def select_courses(courses: List[Tuple[int, int, Set[int]]], k: int, min_credits: int): courses = sorted(courses) n = len(courses) index_of = {cid: i for i, (cid, _, _) in enumerate(courses)} path_indices = [] result = [] def dfs(start: int, credits: int): if len(path_indices) == k: if credits >= min_credits: result.append([courses[i][0] for i in path_indices]) return if len(path_indices) + (n - start) < k: return for i in range(start, n): cid, credit, prereq = courses[i] ok = True for p in prereq: p_idx = index_of[p] if p_idx not in path_indices: ok = False break if not ok: continue path_indices.append(i) dfs(i + 1, credits + credit) path_indices.pop() dfs(0, 0) return result courses = [ (0, 3, set()), (1, 4, {0}), (2, 2, set()), (3, 5, {1}), (4, 3, {2}), (5, 1, set()), ] result = select_courses(courses, k=3, min_credits=8) print(result)

这段代码里最关键的是先修检查。因为组合搜索的下标严格递增，当程序处理到课程i时，所有下标小于i的课程要么已经被选进path_indices，要么已经被之前的循环永久跳过。所以如果某个先修课的编号小于当前课程，却不在path_indices里，说明它已经被跳过，这组课程无论如何都不可能满足先修约束，直接continue掉。

这个剪枝正确的前提是“先修课编号小于当前课程编号”。如果原始数据没有这个性质，比如课程编号是随意的，先修可能在后面才出现，那就不能直接组合搜索了，得改成排列搜索，每次都从全量课程里挑下一个，再用一个selected集合判断先修是否已经出现。那种实现会更慢，但数学模型更通用。实际项目里最好先做预处理，把课程按拓扑顺序编号，既清晰又高效。

6.3 扩展方向：更多剪枝与调试习惯

这个例子的剪枝还可以继续加深。比如计算剩余课程的最高学分总和，如果当前学分加上剩余最大学分都达不到min_credits，那整个分支可以直接返回。这属于“全局上界剪枝”，比单纯检查剩余数量更贴近业务目标。

另外，如果加入时间冲突检查，比如每天最多只能上 4 节课，就相当于给每个递归层加一个更复杂的合法性判断。核心框架不用改，只要在进入下一层前检查一条新约束就好。这就是递归回溯最让我喜欢的地方：基础框架一旦稳定，业务逻辑就像插卡槽一样往里面加条件。

最后分享一个我每次调试递归回溯都会用的小习惯：在dfs第一行打印缩进和当前path。比如print(" " * len(path) + str(path))，这样你能非常直观地看到递归往哪走、在哪个位置回退。等确认路径没问题，再把这个print删掉。这个习惯帮我省了大量时间，也推荐给刚开始学剪枝的朋友。