企业官网建设流程全解析

“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，所以大多数题不会撞上这个限制。但如果你把模板改去解一些更深的搜索问题（比如路径遍历、树形DP），RecursionError就会找上门。

常见的应对是sys.setrecursionlimit(10000)。它能调大上限，但别迷信它。Python的调用栈每层都要占用内存，调得太高容易直接栈溢出崩溃，这个限制是解释器保护自己的机制。我的建议是：第一，先算一下你的递归深度理论上能达到多少，再决定要不要调深；第二，能剪枝把深度降下来，就不要靠调限制撑过去；第三，如果一个问题的递归深度轻松超过3000，最好直接考虑迭代方案。

5.2 记忆化搜索：什么时候值得加、怎么加

排列组合里还有一个常被忽略的优化：记忆化搜索。适用场景是“同一个子问题的结果会被重复计算多次”的状态枚举题，比如组合总和问题里，可能出现大量相同的(start, remain)参数组合。给递归函数加一个缓存字典，遇到相同参数直接返回已算出的结果，能显著减少重复子树的展开。

from functools import lru_cache def combination_sum_memo(candidates, target): candidates.sort() @lru_cache(maxsize=None) 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数组”“为什么这个条件要写在递归前而不是递归后”的粒度，然后用这种拆解过的思路去对付新题目。排列组合只是递归的一小片实验田，但这片田里的每个坑，都会在未来的图搜索、树遍历、状态压缩里原样再现。

最后再分享一个小技巧：遇到新的递归题，先别急着写代码，在纸上画出前三层递归树，标出你要的参数，看它们如何随层数变化。这一步做完，很多题的“选型”问题就自动消失了。这篇就写到这，后续如果有机会，我想继续聊聊递归树的结构怎么帮你调试一切递归程序。