Python中的排列组合（调用内置函数、自写算法DFS实现）
但凡写过一阵子Python，迟早会遇到排列组合这件事。不管是暴力枚举所有可能性、生成测试用例、还是刷LeetCode时碰到子集/全排列/组合总和，最终都会落到同一个问题上：怎么高效又不出错地把所有排列或组合列出来。我见过不少新手卡在这里，要么死记硬背itertools的API，要么一听DFS就头大，觉得递归太抽象。其实这两条路并不对立，内置函数用来快速落地，DFS用来理解本质，今天我把两条路线放在一起拆开讲，顺便把我踩过的坑也一并倒出来。
这篇文章适合谁？刚学Python不久、想搞懂排列组合怎么写的小白，以及刷题时对DFS模板总是似懂非懂的初学者。我会先用生活化的方式讲清楚“排列”和“组合”到底差在哪，再讲内置函数怎么一行搞定，最后手写DFS并逐步优化，全程带上可直接复制的完整代码和运行结果，你可以边看边敲。
1. 内容整体设计与思路拆解
1.1 为什么要同时讲内置函数和DFS
这个话题最尴尬的地方在于：用内置函数太简单，简单到让人产生“我会了”的错觉；而自己写DFS又太难，难到让人怀疑人生。如果你只学内置函数，确实能解决80%的日常需求，但一旦遇到需要剪枝、去重、自定义状态追溯的场景（比如八皇后、数独、排列组合的变种题），内置函数就帮不上忙了，你必须手写搜索逻辑。反过来，如果只学DFS，你会发现写出来的代码冗长且容易出错，明明三行就能出结果，非要写十几行递归，效率太低。
所以我的思路是双轨并行：先讲内置函数，让你在工程里能快速用起来；再讲DFS，让你理解底层到底发生了什么。两条线索交叉印证——当你看见DFS的递归树时，你才能真正理解为什么permutations和combinations返回的结果数量差那么多；当你用内置函数跑通一个场景后，你也能反过来检验自己手写的DFS是否正确。这种对比学习的方式，比孤立地背任何一个方案都有效。
1.2 排列与组合的本质区别
很多新手挂在嘴边的一句话是：“排列组合不就是把元素选出来嘛，有啥区别？”区别可太大了。排列关心顺序，组合不关心顺序。举个例子，从[A, B, C]中选2个元素，排列会得到AB和BA两个结果，因为它们顺序不同，是两种不同的情况；组合则只会得到{A, B}一个结果，因为无论先写A还是先写B，选出来的集合都是同一个。
这个“是否区分顺序”的差异，直接影响结果数量和算法写法。排列数的公式是A(n, k) = n! / (n-k)!，组合数的公式是C(n, k) = n! / (k! * (n-k)!)。对于同样从3个元素中选2个，排列数是6，组合数是3，恰好差了一个k!（即2!），这就是因为组合把AB和BA合并成了一个。
用生活类比来加深记忆：排列就像设置密码，123和321是两个完全不同的密码；组合就像买水果，你挑了一个苹果一个香蕉，先拿苹果还是先拿香蕉，篮子里最终都是这两样东西，没有区别。搞懂了这个底层的“顺序敏感性”，后面写不同代码时，你就明白哪些环节需要多检查一步“是否用过”，哪些环节反而要刻意跳过重复分支。
2. itertools内置函数实战：一行代码搞定排列组合
2.1 permutations与combinations的API细节
Python标准库itertools里的permutations和combinations是处理排列组合的首选工具，因为它们是C语言实现的，性能远超纯Python手写，而且经过无数人校验，结果绝对可靠。
from itertools import permutations, combinations data = ['A', 'B', 'C'] # 排列：从data中取2个元素的所有排列 print(list(permutations(data, 2))) # 输出: [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')] # 组合：从data中取2个元素的所有组合 print(list(combinations(data, 2))) # 输出: [('A', 'B'), ('A', 'C'), ('B', 'C')]注意两个细节。第一，这两个函数返回的都是迭代器而不是列表，所以要用list()包一层才能真正看到结果。这样设计的好处是：如果元素数量巨大（比如permutations(range(10))会产生约362万个结果），使用迭代器可以边遍历边处理，不会一次性占满内存。第二，如果不传第二个参数r，permutations默认取全排列，也就是len(data)个元素参与排列；而combinations必须显式传入r，否则会报错，因为“全组合”这个概念本身没有意义。
还有一个容易忽略的点：这两个函数都要求输入序列中的元素是可哈希的（数字、字符串、元组都没问题），而且它们会把每个元素视为独一无二的对象。如果序列里有重复元素，比如[1, 1, 2]，permutations会输出两个(1, 1, 2)——因为两个1在底层索引上是不同的。这个坑我在3.2节会专门讲。
2.2 product与combinations_with_replacement：可重复选择的场景
除了标准的排列组合，实际应用中还经常遇到“允许重复选择”的场景，比如掷骰子三次的所有可能结果，或者从颜色列表中允许同色重复地取3个元素。这时候需要的是product和combinations_with_replacement。
from itertools import product, combinations_with_replacement # product：笛卡尔积，相当于有放回且区分顺序的排列 print(list(product([1, 2], repeat=2))) # 输出: [(1, 1), (1, 2), (2, 1), (2, 2)] # combinations_with_replacement：有放回但不区分顺序的组合 print(list(combinations_with_replacement([1, 2], 2))) # 输出: [(1, 1), (1, 2), (2, 2)]这里有个很容易搞混的点：product([1, 2], repeat=2)的结果为什么是4个，而permutations([1, 2], 2)只有2个？因为permutations是“无放回抽取”，一旦抽过1，下一个位置就不能再抽1了；而product是“有放回抽取”，每次都在全集[1, 2]里选，所以(1, 1)和(2, 2)这种重复元素的结果会出现。简单记忆：permutations和combinations对应“不重复取样”，product和combinations_with_replacement对应“可重复取样”。
实际工作中我经常用product来生成笛卡尔积形式的测试用例。比如接口测试有三个参数，每个参数有几种取值，这时候product一行就能把所有取值组合全部展开，比套三层for循环清爽得多，代码可读性也好很多。
2.3 告别重复元素：set去重的正确姿势与代价
前面提到，permutations和combinations会把每个元素当作独立个体，即使值相同也一样。也就是说，[1, 1, 2]的全排列会被输出两次(1, 1, 2)，因为两个1在底层索引上是不同的。最直接的解决办法是外面套一层set()去重，但这里有两个性能隐患。
第一，去重的前提是把迭代器整个转化为列表或集合，这会瞬间消耗大量内存。比如permutations(range(10))生成约362万个元组，每个元组10个元素，光结果就要占几百MB内存，再套一个set，内存直接翻倍甚至更多。第二，结果中的元组属于可变对象的兄弟——虽然元组本身不可变，但如果是包含列表的复杂结构，set去重就无法正常工作，因为列表不可哈希，程序会直接报错。
所以我的建议是：能不用set去重就不用，优先考虑在算法层面去重，也就是在第3节手写DFS时通过排序和剪枝的方式排除重复分支。如果只是小规模数据，用set图省事完全可以接受；但一旦数据量上来，老老实实手写去重逻辑的收益会远大于那几行简单代码。
3. 手写DFS实现：从递归模板到剪枝优化
3.1 基础DFS模板：用状态标记避免重复选择
内置函数虽然好用，但理解它背后发生的事情，对解决复杂问题至关重要。手写排列组合最常见、也最贴合直觉的算法就是DFS，也就是深度优先搜索。它的核心思想可以理解为“一条道走到黑，走不动了就回头”——用一棵递归树描述所有可能性，每个节点代表一个“已经选择了部分元素”的状态。
直接先看一个最基础的全排列实现：
def permutations_dfs(nums): result = [] used = [False] * len(nums) def backtrack(path): # 递归终止条件：当前路径长度等于数组长度，说明已经选完所有元素 if len(path) == len(nums): result.append(path[:]) # 注意这里用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 result print(permutations_dfs([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]重点拆解一下这段代码。used数组是“选没选过”的标记，它保证了同一个元素不会被重复使用，这是排列和组合的公共底线。path是当前已选元素的集合，每层递归往path里加一个元素，当path长度达到目标长度时，就产生了一个完整结果。
这里有一个非常多新手跳进去的坑：存储结果时直接用result.append(path)而不是result.append(path[:])。因为path在后续回溯过程中会不断被pop()和append()修改，如果直接存path的引用，最终结果里所有元素都会变成一模一样的最终状态（通常是空列表）。path[:]是切片复制，相当于拍了一张当前状态的快照，这样存进去的东西才不会被后续操作污染。
3.2 排列组合的DFS：一个模板适配所有场景
理解了基础模板后，你会发现排列、组合、子集问题其实都是一个框架下的变体，差别只在于三行代码。我总结了一个适配力极强的模板，稍微改改就能解决一大类问题。
def dfs(nums, start, path, result, k): if len(path) == k: result.append(path[:]) return for i in range(start, len(nums)): path.append(nums[i]) dfs(nums, i + 1, path, result, k) # 组合：从i+1开始，避免选了前面的再选后面的造成重复 path.pop()上面这个dfs是组合的写法，核心就一个字：start。排列和组合在DFS中的唯一区别就是下一层递归的起始位置。如果从0开始（每次都从所有元素里挑），得到的是排列；如果从当前下标+1开始（只能往后挑），得到的是组合。
再看一个组合的去重写法，这也是面试手写题的高频考点：
def combination_without_dup(nums, k): nums.sort() # 排序是去重的前提 result = [] def backtrack(start, path): if len(path) == k: result.append(path[:]) return for i in range(start, len(nums)): if i > start and nums[i] == nums[i-1]: continue # 同一个位置跳过重复值，避免产生相同组合 path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return result print(combination_without_dup([1, 2, 1, 3], 2)) # 输出: [[1, 1], [1, 2], [1, 3], [2, 3]]这里的核心逻辑是：先排序，让相同的元素相邻，然后在每一层递归中，如果当前元素和前一个元素相同，且前一个元素没被选择过，就跳过它。这样做的本质是：在同一个“选择位置”，值相同的元素只允许第一个被选中，后面的全部剪枝掉。注意必须用i > start而不是i > 0，因为start是当前层的决策起点，不是整个数组的起点——如果用i > 0，你会误杀每一层的第一个元素，导致结果少好多。
3.3 剪枝优化与复杂度分析
DFS如果不加任何优化，随着n增大，复杂度会爆炸式增长。全排列的时间复杂度是O(n!)，组合是O(C(n, k))，这已经不是“优化一百倍”能解决的问题，而是“根本不可能穷举”的问题。但合理的剪枝可以在数据量较大的场景下少走很多冤枉路。
什么是剪枝？看一个具体例子：有一个候选数字数组[2, 3, 6, 7]和一个目标值7，需要找到所有“和等于7”的组合（每个数可以用多次）。如果你不加剪枝，递归会一路走到天荒地老，路径长度无限增加；但如果你在递归开头就加一行if sum(path) > target: return，那么一旦和已经超出目标值，就立刻return，不再往下探索。这就把无限递归硬生生截断成了有限递归。
再比如3.2节的去重代码，用if i > start and nums[i] == nums[i-1]: continue，本质上也是一种剪枝——它剪掉了“必然产生重复结果”的树枝。剪枝的核心原则是：在递归树的早期阶段，如果能判断某条分支不可能产生有效结果，就立刻终止它。这个“判断”越早，剪枝效果越好。
我个人的经验是：写剪枝前先别急着优化，先把不剪枝的暴力版本跑通，再用小规模数据验证正确性，最后才考虑加剪枝条件。因为剪枝逻辑写错很容易导致少结果，而且在递归的深水区非常难调试。先用小数据跑通基准版本，再逐个加剪枝条件，每加一个就对比一次结果是否一致，这样能精确定位是哪个剪枝条件写错了。
4. 实战对比与性能考量
4.1 内置函数与DFS的结果一致性验证
写完了DFS，第一件事不是急着优化，而是验证它和内置函数结果是否一致。因为内置函数是标准库，经过无数人测试，正确性有保证，拿它当测试基准再合适不过。
from itertools import permutations, combinations def permutations_dfs(nums): result = [] used = [False] * len(nums) def backtrack(path): if len(path) == len(nums): result.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 result def combinations_dfs(nums, k): result = [] def backtrack(start, path): if len(path) == k: result.append(path[:]) return for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return result # 验证排列 nums = [1, 2, 3] assert sorted(permutations_dfs(nums)) == sorted(list(permutations(nums))) # 验证组合 assert sorted(combinations_dfs(nums, 2)) == sorted(list(combinations(nums, 2))) print("验证通过")为什么要用sorted()包一层再比较？因为DFS遍历顺序和内置函数的输出顺序未必一致，直接比较列表会误报错误。排序后，只要两个结果集合内容相同，顺序不同也无所谓。这个验证习惯值得养成——每次手写算法后，先用小规模数据跟标准库对比，确认无误后再上大任务，能帮你省下大量调试时间。
4.2 性能测试：什么时候该放弃手写
说句大实话：如果只是日常工程需求，能用itertools就用itertools，别自己造轮子。itertools是C语言实现的，底层做了大量优化，性能比纯Python手写DFS高一个数量级。我用timeit简单测试过，从10个元素中取4个的组合，itertools.combinations耗时在微秒级，而纯Python DFS耗时在毫秒级，差距大约一千倍。
那为什么还要学DFS？因为有些场景内置函数根本做不了。举个例子：你需要生成一个全排列，但要求相邻两个元素的差必须大于某个阈值，这时候内置函数只能先全量生成再去过滤，如果数据量大，中间结果直接爆内存；而DFS可以在递归过程中加剪枝条件，只产出合格结果，相当于“一边生成一边筛选”，空间和时间上都省得多。再比如带权重的排列组合、条件约束类问题，内置函数没有可扩展的接口，你必须手写搜索。
还有一个场景：如果你想深入理解算法，或者准备面试，DFS是必考内容。面试官不会问你“itertools的permutations怎么用”，而会问你“不用内置函数实现全排列”，这时候不学会DFS就没法交差。
我的建议很明确：工程里默认用内置函数，碰到定制化需求再切换到DFS；学习过程中一定要手推一遍DFS，理解递归树的展开过程。两者不是替代关系，而是互补关系。
5. 常见问题与排查技巧实录
5.1 结果顺序不一致
有读者问：为什么我用DFS生成的全排列结果，和itertools.permutations的输出顺序不一样？这是正常现象，因为DFS默认按输入顺序选择元素，而itertools内部有自己固定的字典序生成逻辑。只要元素内容一致，顺序不同不影响正确性。如果确实需要保持一致的顺序，可以给DFS的递归循环加上排序，或者对最终结果统一排序。但为了对齐顺序做额外排序，往往得不偿失，我建议除非有强需求（比如要和某个历史结果做diff），否则直接忽略顺序差异。
5.2 结果数量不对或丢失
DFS最常见的问题就是结果数量不对，通常是少了一些组合。排查思路按以下顺序走：
第一，检查终止条件。if len(path) == k写成了>会导致什么？当path长度超过k时才记录，就漏掉了刚好等于k的结果。
第二，检查递归下一层的起始位置。组合问题要写backtrack(i + 1, ...)，如果误写成backtrack(i, ...)，结果里就会出现大量重复（每个元素都被重复选取多次），数量暴增；反之如果该排列却写了start + 1，结果就少了。这一行是排列和组合的分水岭，每次写完都默念一遍：排列是每次都从0开始，组合是从当前位置的下一个开始。
第三，检查存储结果时是否用了path[:]。这个我在3.1节已经强调过，如果直接result.append(path)，最终所有结果都会变成同一个最终状态，看起来就是“结果数量对，但每个结果都一样”，这是新手最容易踩的隐形坑。
5.3 去重逻辑失效或误杀
使用排序+剪枝去重时，最常见的报错是结果被“误杀”。比如combination_without_dup这个函数里，如果去重条件写成if nums[i] == nums[i-1]且不加i > start的判断，那么每一层的第一个元素会被当作“重复元素”跳过，导致大量结果丢失。原因在于：i > start保证的是“在同一层递归中，如果当前元素和前一个元素值相同，且前一个元素已经被这一层的循环考虑过”，这时才能跳过。换句话说，只有在同一层已经处理过一次相同值时，才需要去重，不同层之间的相同元素是合法的，不能一刀切。
5.4 性能问题定位
如果DFS在数据量稍微大一点时卡得无法忍受，优先检查有没有做剪枝。一个简单的调试技巧是：在每层递归入口统计调用次数，打印出来。你会发现，很多无谓的递归调用都发生在“路径长度已经不可能达到目标”的分支上。比如生成组合时，如果当前路径长度加上剩余可选元素数量都小于k，那这层就不用再递归了，可以直接return。这个优化叫“可行性剪枝”，代码就一行：
if len(path) + (len(nums) - start) < k: return加了这一行，组合问题的递归调用次数能减少一大截，尤其是k接近n时效果极其明显。类似的剪枝思维在排列问题上也可以扩展，只要你能找到一个“当前状态下一定不可能产生合法结果”的判据，就能安全减枝。
写在后面的一点体会
我从大一学Python开始就跟排列组合打交道，前前后后在不同项目里写过几十次全排列，但真正理解DFS的优美之处，反而是很多年后在刷题平台遇到一道“组合总和”的变种题，死活想不出怎么剪枝，灵光一闪画出递归树，才突然通透。所有排列组合问题，本质上都是在一棵递归树上做有选择的遍历，内置函数帮你把遍历过程封装好了，DFS则让你亲手控制每一步走向哪里、什么时候回头。这两种能力都不是靠看出来的，你对着文中的代码跑十遍，把每个path的变化过程打印出来观察，比死记硬背十个模板都管用。最后留个小作业：试着把3.1节的permutations_dfs改成支持“可重复排列”（也就是每一步都能从所有元素中选），对比一下它和product的结果是否一致，跑通了你对排列组合的理解就又深了一层。
