“Python求排列组合”这个主题我连着写了三篇递归系列每次发布都有读者在评论区说代码看懂了自己写还是卡壳。到了第4篇我打算把节奏放慢一点不再从递归的底层原理讲起而是集中精力拆“排列组合”这个具体战场里的细节问题为什么全排列需要used数组而组合只需要一个start索引、重复元素到底该在哪个位置去重、剪枝应该剪在第几步、递归在什么情况下该让位于迭代。这一篇的内容适合已经能默写出全排列和组合模板、但总觉得自己还差一层“通透”的读者。如果你是第一次接触递归建议先把本系列前三篇的骨架过一遍再来。这里的每个技巧都默认你已经熟悉“递出去、归回来”这个基本动作。1. 第4篇的开场白把“排列组合”这盘棋的棋子摆清楚1.1 前几篇留下的接口全排列与组合的两份最小骨架前几篇我们反复聊过递归的两个最基本动作一个是“递出去”一个是“归回来”。放到排列组合里这盘棋的棋盘就是两类经典代码模板。先看全排列的最小骨架它的核心是“每个位置都试一遍所有还没用过的元素”def permute(nums): res [] path [] used [False] * len(nums) def dfs(): 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.pop() used[i] False dfs() return res再看组合的最小骨架。组合只关心“从n个数里选k个”不关心顺序所以它不需要used数组取而代之的是一个start索引保证每次只从“当前数字后面”继续选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这两份代码放在一起其实很多读者第一眼就能看出不同全排列的递归函数签名是dfs()没有参数它靠used数组判断“还有哪些元素可用”组合的递归函数签名是dfs(start, path)它通过start控制“下一次从哪个位置开始扫描”。一个管“用没用过”一个管“还能不能选”这就是递归状态设计的两种典型思路。而这两份代码又是同一个母体的孪生兄弟都用了“路径path 结果收集res”的标准回溯模式都是在递归到底部时把path的副本append进res都遵循“做选择 - 递归 - 撤销选择”的铁三角。把这个三角形刻在脑子里后面所有的变形题都是在这个骨架上加装饰。我在带人学递归时经常让他们把这两段代码各自跑一遍然后回答三个问题第一如果把组合里的dfs(i 1)改成dfs(start 1)会怎样第二如果把全排列里的used数组去掉会看到什么样的输出第三为什么组合收集结果时判断的是len(path) k而全排列判断的是len(path) len(nums)这三个问题想明白了排列组合的递归骨架才算真正长在脑子里而不是背下来的。1.2 “位置视角”和“元素视角”两条递归路线的分野全排列的本质是站在“位置”上看问题第一个位置放谁第二个位置放谁……第n个位置放谁所以递归树的每一层对应一个位置每个位置都要在所有未使用的元素中做选择。这就是“位置视角”它天然需要used数组来记录哪些元素已经被人占了。组合的本质是站在“元素”上看问题第一个元素选不选第二个元素选不选……第n个元素选不选或者等价地说当前从第几个元素开始“往后”还能选几个。这是“元素视角”它用start索引来保证“不回头”从而自动避免顺序重复。这两种视角的分野直接决定了代码里一个关键变量的存在与否。说一个实际现象很多人看完排列模板想改成组合时第一反应是把if used[i]: continue这个判断直接删掉。结果会得到“包含所有顺序排列”的错误答案。原因很简单全排列去掉used每个位置仍然会从头扫描所有元素自然会把[1,2]和[2,1]都算进来而组合要求的是“从我当前的位置往后看”必须靠start才能强制方向性。用生活化的类比来说全排列像给一群客人安排座位你手里得有一张“谁已经坐下”的名单组合像在自助餐厅的取餐区走一趟你只需要记得“走到哪个餐台了”不用回头因为回头已经没有意义了。这种“位置/元素”视角的区分看起来小却是本系列后面所有进阶问题的起点。比如去重为什么组合用i start判断、全排列要用not used[i - 1]判断根源就在这两种视角的差异上。这部分我会在下一章展开。2. 重复元素上场去重的三个层次与常见翻车现场2.1 先排序再递归去重的前提条件当输入数组里出现重复元素时比如[1, 2, 2]全排列或组合的结果里就会冒出很多“看起来一样”的答案。最直接的思路是用一个哈希集合去重每次得到一个新的排列送去重器过一遍。这个方法能跑但性能差而且失去了递归程序该有的“结构美”。真正的处理方式是“排序 剪枝”先把参与递归的元素排序让相同的元素紧挨在一起然后在递归树展开时利用“相同元素只会出现在相邻位置”这个特性决定要不要跳过。排序这一步是整个去重策略的前提缺了它后面所有基于相邻性的判断都会失效。为什么排序管用因为在一个有序序列里所有值相同的元素必然相邻。当我们在一层递归里从左到右扫元素时如果发现“当前元素和上一个相同而且上一个已经被处理过”就说明当前元素是上一个元素的重复品应该直接跳过。这个逻辑说起来简单实现时却有层次之分下面分开讲。2.2 组合去重同层跳过与“i start”的边界感组合的去重写法是递归界最常用的“同层去重”。以“带重复元素的子集”为例def subsets_with_dup(nums): nums.sort() res [] path [] def dfs(start): res.append(path[:]) for i in range(start, len(nums)): if i start and nums[i] nums[i - 1]: continue path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res关键就在if i start and nums[i] nums[i - 1]这一行。很多初学者会把条件写成if nums[i] nums[i - 1]结果发现第一个重复元素也被跳过了答案丢失。原因在于i start限定了“跳过”只发生在同一层递归的后续兄弟分支之间而不是发生在跨层的父子分支之间。什么叫“跨层”和“同层”拿[1, 2, 2]举例。递归树从空路径出发第一层会依次选择1、2、2第二个2会被跳过。当你选择了第一个2之后递归进到下一层这一层里start指向第一个2后面的位置也就是第二个2的位置这时候i start虽然nums[i] nums[i - 1]成立但这个2是“新一层递归里的第一个选择”它必须被允许使用——否则[2, 2]这个真正合法的子集就永远产生不出来了。这个“同层 vs 跨层”的边界是去重最容易翻车的地方。我的排查技巧是当去重结果少答案时优先检查条件里有没有i start当结果多答案时检查是不是漏掉了used数组的配合在全排列场景里更容易出现这种问题。2.3 全排列去重used数组里那个“not used[i - 1]”的微妙判断全排列去重的经典写法是排序 used数组 同层判断def permute_unique(nums): nums.sort() res [] path [] used [False] * len(nums) def dfs(): 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.pop() used[i] False dfs() return res这里初学者最容易卡住的就是not used[i - 1]这个条件。为什么全排列去重要额外判断“前一个相同元素还没被使用”我先把结论摆出来i 0 and nums[i] nums[i - 1] and not used[i - 1]表达的是“当前元素和上一个元素值相同而且上一个元素还没被选过那么当前元素必须跳过”。它的作用是强制所有相同元素按固定顺序出场保证它们在结果中的相对位置唯一。为什么非要“上一个还没被选过”才跳过因为当上一个相同元素已经被选走、正在递归深层时当前这个元素是可以选的——它是在“补已经上场的那个元素的空缺”。如果这里不判断not used[i - 1]而是盲写if i 0 and nums[i] nums[i - 1]那么当上一个元素已经被使用但还没撤销时当前元素也会被当成重复品跳过结果就是某些合法排列找不齐。我见过不少人在这个条件上纠结半天最后干脆用“先排列再去重set”绕过去。能用但失去了递归程序那种“边搜索边杜绝重复”的优雅。我的建议是把used[i - 1]想象成“上一个相同元素的出场标记”not used[i - 1]就是“上一个还没登场你抢先登场了不允许”。这样记比死背代码稳定得多。3. 剪枝时机递归从“能算完”到“算得快”的分水岭3.1 组合总和II中的排序剪枝去重解决的是“结果正确性”剪枝解决的则是“效率”。写递归程序时很多人只关心层数到了没有却忽略了那些完全没必要的递归分支——它们会让程序从小规模用例秒出变成大规模用例卡死。剪枝的本质就是让递归树“长得更瘦”。组合总和II是剪枝的绝佳教材。题目要求给定候选数组可能有重复数字和目标数target找出所有和等于target的组合每个数字在每个组合里只能用一次。经典实现如下def combination_sum2(candidates, target): candidates.sort() res [] path [] def dfs(start, remain): if remain 0: res.append(path[:]) return for i in range(start, len(candidates)): if i start and candidates[i] candidates[i - 1]: continue if candidates[i] remain: break path.append(candidates[i]) dfs(i 1, remain - candidates[i]) path.pop() dfs(0, target) return res这里有两处剪枝一是同层去重if i start and candidates[i] candidates[i - 1]它阻止重复组合的出现二是排序后的大数剪枝if candidates[i] remain: break它利用“剩余可选值越来越大的顺序性”直接中断整层循环。第二个剪枝为什么用break而不用continue因为候选数组已经排过序当前元素如果已经大于剩余目标值后面所有元素只会更大没有一个能满足条件所以整层循环都没有继续的必要直接break。这一行是“排序后剪枝”的灵魂——排序不只为了去重更为了给剪枝创造单调性。如果输入数组本身就是乱序的后面可能出现“前面大、后面小”的情况那这里就只能用continue而不能用break了。3.2 剩余元素不足时的提前收刀还有一种剪枝发生在“递归还没到达预期深度但已经注定填不满”的场景。比如组合问题里当前路径长度是len(path)还需要k - len(path)个元素而start之后能提供的元素只剩下len(nums) - start个如果剩余候选数不够填满所需位置这层递归再怎么走都是死路可以直接返回。写成代码就是if len(path) (len(nums) - start) k: return这行判断放在dfs的开头比放在循环里更高效因为它一进入函数就提前拦截省掉了对整层循环的遍历。我在实际测试中发现这种剪枝对k接近n的用例特别有效能把递归树的高度和宽度同时压缩。这类“剩余量不足”的剪枝思路源头是“可行性剪枝”在每一步都问自己沿着当前这条路径继续走还有没有可能形成合法答案如果答案是“必然不可能”就立刻回头只有当“有可能”时才继续深入。数据规模小的递归题看不出差距一旦数据量上来这行提前return能帮你省掉上万次无意义的函数调用。3.3 剪枝和回溯一个前瞻一个后撤新手容易把“剪枝”和“回溯”当成一回事其实它们作用在不同的时间点上。回溯是“递归返回时撤销选择”它发生在一条路径走完之后把path和状态恢复成递归前的样子让其他分支能继续使用这些状态剪枝是“在进入某个分支之前就判断这条路能不能走通”能走通就进走不通就不进连递归都不用发生。可以这样理解回溯是“后撤”剪枝是“前瞻”。一个在出口处回收战场一个在入口处闭目探路。两者结合才是一个完整的递归搜索策略。光有回溯没有剪枝程序能跑但效率平庸光有剪枝没有回溯状态会在多个分支间互相污染结果一塌糊涂。我在写剪枝时有一个习惯先把不剪枝的版本跑通确认答案正确再逐层加剪枝每加一处就重新跑一遍验证答案没变。这样既能保证剪枝逻辑不破坏正确性又能看清每个剪枝到底砍掉了多少分支。如果一上来就写满剪枝代码一旦出错你很难判断是剪枝剪错了还是递归骨架本来就错了。4. 排列组合的骨架怎么迁移到更复杂的递归问题4.1 N皇后全排列的“位置填充”思维变形学递归最怕的是“会背模板换个场景就懵”。排列组合的模板看似只解决两类题其实它的思维可以迁移到一大堆“搜索类”问题上N皇后就是很好的例子。N皇后问题的本质是在N×N棋盘上放N个皇后让它们互相不攻击。如果从递归视角看它的骨架和全排列高度相似——每一行放一个皇后这不就是“第i个位置放哪个元素”的思路吗区别在于全排列的判断条件是“这个元素用没用过”而N皇后的判断条件是“这个列、两条对角线是否安全”。def solve_n_queens(n): res [] cols [False] * n diag1 [False] * (2 * n - 1) diag2 [False] * (2 * n - 1) board [] def dfs(row): if row n: res.append(board[:]) return for col in range(n): d1 row - col n - 1 d2 row col if cols[col] or diag1[d1] or diag2[d2]: continue cols[col] diag1[d1] diag2[d2] True board.append(. * col Q . * (n - col - 1)) dfs(row 1) board.pop() cols[col] diag1[d1] diag2[d2] False dfs(0) return res你看整个结构和全排列的“used数组 路径 撤销选择”几乎一模一样只是把used数组从一维变成了三个维度列、主对角线、副对角线。如果你能看懂全排列模板这个N皇后版本应该也能一眼看透。这就是递归程序设计的“艺术”所在骨架是同一副换的是“约束条件的表达方式”。4.2 括号生成从“选与不选”到“左右配平”括号生成问题要求给定n对括号生成所有合法的括号组合。它看起来和排列组合毫无关系但递归骨架同样是那套“做选择、递归、撤销选择”的铁三角。只是这里的“选择”变成了当前位置是放“(“还是放”)”。def generate_parenthesis(n): res [] def dfs(left, right, path): if len(path) 2 * n: res.append(path) return if left n: dfs(left 1, right, path () if right left: dfs(left, right 1, path )) dfs(0, 0, ) return res两个剪枝条件值得琢磨left n保证左括号数量不能超过n对right left保证右括号数量不能超过已出现的左括号数量——这是括号合法的核心约束。如果去掉right left你会得到一堆括号不配对的非法串。你会发现这个“合法性判断”其实就是排列组合里“used”和“start”的变形它也是在限制“下一个可选项的范围”。4.3 电话号码组合递归参数从“选到哪里”变成“走到哪组”还有一类题输入不再是“一个数组里选元素”而是“多个集合各选一个元素”比如电话按键的字母组合。每个数字对应一小组字母要求把所有可能的组合列出来。它的递归骨架其实是“组合模板”的多集合版本。def letter_combinations(digits): if not digits: return [] mapping { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz } res [] def dfs(index, path): if index len(digits): res.append(path) return for ch in mapping[digits[index]]: dfs(index 1, path ch) dfs(0, ) return res这里的递归参数从“start索引”变成了“index索引”但两者意义完全不同组合的start是控制系统内元素的选择范围电话号码的index是控制外部映射表推进到第几位。两个索引看似都是int代表的却是两种不同的“状态位置”。你在写这类题时一定要先问自己我递归的参数到底代表什么是“当前处理到第几组”还是“当前从哪个元素开始选”这决定了递归树下钻的方式。这三类迁移题放在一起是想强调一件事排列组合的递归程序表面上是在解决具体的计数问题深层是在训练“状态设计”能力。所谓递归程序设计艺术本质上就是设计出能精确描述问题状态的参数集合再让递归树自然生长。5. 性能边界与工程化取舍递归不是银弹5.1 Python递归深度限制与setrecursionlimit的真实边界写递归绕不开一个现实问题Python对递归深度默认限制在1000层左右。排列组合这类问题递归深度一般等于n或k所以大多数题不会撞上这个限制。但如果你把模板改去解一些更深的搜索问题比如路径遍历、树形DPRecursionError就会找上门。常见的应对是sys.setrecursionlimit(10000)。它能调大上限但别迷信它。Python的调用栈每层都要占用内存调得太高容易直接栈溢出崩溃这个限制是解释器保护自己的机制。我的建议是第一先算一下你的递归深度理论上能达到多少再决定要不要调深第二能剪枝把深度降下来就不要靠调限制撑过去第三如果一个问题的递归深度轻松超过3000最好直接考虑迭代方案。5.2 记忆化搜索什么时候值得加、怎么加排列组合里还有一个常被忽略的优化记忆化搜索。适用场景是“同一个子问题的结果会被重复计算多次”的状态枚举题比如组合总和问题里可能出现大量相同的(start, remain)参数组合。给递归函数加一个缓存字典遇到相同参数直接返回已算出的结果能显著减少重复子树的展开。from functools import lru_cache def combination_sum_memo(candidates, target): candidates.sort() lru_cache(maxsizeNone) def dfs(start, remain): if remain 0: return [[]] paths [] for i in range(start, len(candidates)): if candidates[i] remain: break for sub in dfs(i 1, remain - candidates[i]): paths.append([candidates[i]] sub) return paths return dfs(0, target)但注意记忆化搜索适合“只求数量、不求具体路径”或“路径可安全复用”的题目。在需要收集所有具体组合、每条path都要单独保存的经典排列组合题里记忆化几乎派不上用场因为路径本身和递归状态绑定无法简单复用。所以要不要加记忆化取决于你的目标是“计数”还是“枚举”。5.3 迭代替代方案什么时候应该放弃递归递归最大的软肋是调用栈开销和编写时的思维负担。有些场景用迭代反而更清晰。比如生成全排列时可以用迭代“插入法”——从空排列开始每轮把新元素插入到已有排列的所有空位。也可以直接用Python标准库的itertools.permutations和itertools.combinations两行解决战斗import itertools perms list(itertools.permutations([1, 2, 2])) combs list(itertools.combinations([1, 2, 3, 4], 2))我个人不排斥工具库。实际工作中如果只是为了快速拿到排列组合结果首选永远是标准库只有在需要深度定制比如剪枝、去重、带约束搜索时才值得手写递归。这也是一种工程化取舍递归程序的价值不只是“能算出答案”更在于“能在计算过程中嵌入业务规则”。结尾按我一直以来的学习节奏这篇最想留给你的建议是把递归程序当成一种“思维方式”来练而不是当成“代码模板”来背。我见过不少朋友把全排列模板背得滚瓜烂熟换一道“组合总和”就又不会了。真正有效的方法是像本文这样把每个模板拆到“为什么这里要有个used数组”“为什么这个条件要写在递归前而不是递归后”的粒度然后用这种拆解过的思路去对付新题目。排列组合只是递归的一小片实验田但这片田里的每个坑都会在未来的图搜索、树遍历、状态压缩里原样再现。最后再分享一个小技巧遇到新的递归题先别急着写代码在纸上画出前三层递归树标出你要的参数看它们如何随层数变化。这一步做完很多题的“选型”问题就自动消失了。这篇就写到这后续如果有机会我想继续聊聊递归树的结构怎么帮你调试一切递归程序。