1. 为什么排列组合值得单独开一个系列来整理排列组合这四个字很多人第一次听到是在高中课堂第二次听到就是在面试或者实际项目里被卡住的时候。我做了十多年开发带过不少新人发现一个很普遍的现象动态规划、二分查找、图论这些大家反而会主动去刷题、去总结模板但排列组合往往被当成数学题跳过。结果一到真实场景——比如写一个批量生成测试用例的工具、做一个活动奖品分配逻辑、实现一个可配置的报表维度组合——就发现脑子里那点零散的公式根本不够用。这个系列我想做的事情很明确把排列组合从数学课本里的公式变成能直接写进代码里的算法套路。它解决的核心问题是——当你面对从一堆元素里挑几个、排个序、允许不允许重复这类需求时能立刻判断出属于哪一类套用哪个模板复杂度大概是多少边界情况在哪里。适合谁看刚入行的开发者、准备面试的同学、以及工作中偶尔要处理组合枚举逻辑的工程师。哪怕你数学基础一般只要会写循环和递归这个系列就能让你把这块补起来。我整理的时候刻意避开了纯数学推导重点放在算法怎么落地上。因为实际写代码时你需要的不是证明公式而是知道用回溯还是用迭代、什么时候要剪枝、去重该怎么处理。这些才是真正卡人的地方。2. 排列组合的四大基本类型与判定方法2.1 先搞清楚你到底在求什么排列组合的题目千变万化但归根结底就四个维度在组合取不取全部元素、顺序重不重要、元素能不能重复用、原数组有没有重复元素。把这四个维度理清楚题目基本就归类了。我习惯用一个简单的判定流程先问结果里元素的顺序变了算不算新答案算就是排列不算就是组合再问同一个元素能不能被选多次能就是可重复不能就是不可重复。这两问一答四类基本型就出来了。类型顺序敏感可重复选取典型问题全排列是否把n个数所有排法列出来组合否否从n个数里选k个可重复排列是是密码锁所有可能可重复组合否是凑硬币面额组合这个表格建议直接记住。我面试别人的时候经常让对方先判断题目属于哪一格判断对了思路基本就顺了判断错了后面写得再花哨也是白搭。2.2 为什么顺序和重复这两个维度最关键顺序决定了你用不用标记已访问。排列类问题里每个位置放哪个元素是有讲究的所以你需要一个used数组记录哪些元素已经被放到当前路径上。组合类问题里顺序无所谓所以通常用一个start索引保证只往后选天然避免重复。重复性决定了你的循环起点。不可重复选取时下一层递归从i1开始可重复选取时下一层还从i开始因为当前元素还能再用。这个i和i1的区别是排列组合代码里最容易写错的地方我见过太多人在这里翻车。提示判断题目类型时先别急着写代码拿一张纸把顺序重复两个问题写下来答案确定了再动手能省掉大量调试时间。2.3 复杂度心里要有个数排列类问题的结果数量是阶乘级的n10 的时候全排列就有 360 多万种n15 直接上万亿。所以排列组合算法本质上都是指数级或阶乘级复杂度不存在多项式解法。这一点必须提前认清否则你会误以为自己的代码效率低其实是问题本身就这么大。组合类问题结果数量是组合数 C(n,k)比阶乘温和一些但 k 接近 n/2 时依然爆炸。实际工程里遇到这类需求第一反应应该是真的需要枚举全部吗能不能用剪枝、能不能只求计数不求枚举、能不能用动态规划替代。这个意识比会写模板更重要。3. 全排列的三种实现与去重处理3.1 回溯法最通用也最好理解的写法全排列的标准解法是回溯。核心思路是维护一个当前路径path和一个已使用标记used每层递归尝试把一个还没用过的元素放进路径放满 n 个就收集结果。def permute(nums): res [] used [False] * len(nums) def backtrack(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]) backtrack(path) path.pop() used[i] False backtrack([]) return res这段代码我建议背下来。它的结构——选择、递归、撤销选择——是所有回溯类问题的通用骨架。你把这个骨架吃透子集、组合、分割回文串这些题都是同一个模子。path[:]这里必须拷贝不能直接 appendpath。因为 path 是引用后续会被修改直接存进去最后全是空列表。这个坑我当年踩过调了半天才反应过来。3.2 交换法省掉 used 数组的写法另一种常见写法是交换法把数组分成已确定前缀和待排列后缀两部分每层递归把当前位置和后面的元素依次交换。def permute_swap(nums): res [] def backtrack(start): if start len(nums): res.append(nums[:]) return for i in range(start, len(nums)): nums[start], nums[i] nums[i], nums[start] backtrack(start 1) nums[start], nums[i] nums[i], nums[start] backtrack(0) return res交换法的好处是不用额外开 used 数组空间上省一点。但它有个隐患当原数组有重复元素时直接交换会产生重复结果需要额外去重。所以如果题目明确说元素互不相同交换法很优雅如果有重复我更倾向用回溯加排序去重。3.3 有重复元素时怎么去重这是全排列里最容易出错的部分。假设数组是[1,1,2]直接回溯会得到重复结果。标准做法是先排序然后在每层递归里加一个判断如果当前元素和前一个元素相等且前一个元素还没被使用就跳过。def permute_unique(nums): nums.sort() res [] used [False] * len(nums) def backtrack(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]) backtrack(path) path.pop() used[i] False backtrack([]) return res那个not used[i-1]的条件是精髓。它的含义是如果前一个相同元素还没被用说明当前这个元素是同一层里的重复选择跳过如果前一个已经被用了说明是不同层的正常选择允许。这个逻辑我建议多画几遍递归树去理解光看代码容易记混。注意去重前一定要排序。不排序的话相同元素不相邻nums[i] nums[i-1]这个判断就失效了。这是很多人忽略的前提。4. 组合问题的剪枝与去重技巧4.1 从 n 个数里选 k 个的标准模板组合问题的核心是不回头选用一个start参数控制每层从哪个位置开始遍历保证选出来的组合是按索引递增的天然去掉了顺序带来的重复。def combine(n, k): res [] def backtrack(start, path): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) backtrack(i 1, path) path.pop() backtrack(1, []) return res注意递归调用是backtrack(i 1, path)不是start 1。用i 1才能保证下一层从当前选中元素的下一个开始用start 1就错了。这个细节我在代码 review 里见过好几次。4.2 剪枝让不可能的分支提前结束组合问题有个非常实用的剪枝如果剩下的元素数量已经不够凑满 k 个了就没必要继续递归。具体来说在循环里i的上界可以收紧。原本循环是for i in range(start, n 1)剪枝后变成for i in range(start, n - (k - len(path)) 2):这个上界怎么来的当前还需要选k - len(path)个元素从i到n必须至少有这么多元素所以n - i 1 k - len(path)解出i n - (k - len(path)) 1range 右开所以加 2。这个剪枝在 n 大 k 小的时候效果极其明显。我实测过 n20、k3 的情况不剪枝要遍历大量无效分支剪枝后递归次数直接降一个量级。别小看这一行它是组合问题从能跑到跑得快的关键。4.3 组合总和类问题的去重套路组合总和是组合问题的进阶版典型场景是从候选数组里选若干个数使和为 target每个数可重复选。这类题分两种候选数组无重复元素、候选数组有重复元素。无重复元素时递归传i而不是i1允许重复选当前元素def combination_sum(candidates, target): res [] candidates.sort() def backtrack(start, path, remain): if remain 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remain: break path.append(candidates[i]) backtrack(i, path, remain - candidates[i]) path.pop() backtrack(0, [], target) return res有重复元素时除了排序还要加同层去重判断if i start and candidates[i] candidates[i-1]: continue。注意这里是i start而不是i 0因为我们要跳过的是同一层里的重复而不是跨层的重复。这个区别和全排列去重是同一个道理但条件写法不同容易混淆。提示candidates[i] remain时直接 break是因为数组已排序后面的只会更大。这个剪枝能砍掉大量无效分支比 continue 更高效。5. 可重复排列与可重复组合的实战场景5.1 可重复排列密码锁与笛卡尔积可重复排列的典型场景是密码锁、验证码枚举、多维度参数组合。它的特点是每个位置都可以从全部元素里选不受 used 限制。def permute_repeat(nums, k): res [] def backtrack(path): if len(path) k: res.append(path[:]) return for num in nums: path.append(num) backtrack(path) path.pop() backtrack([]) return res这段代码和全排列的区别就一处没有 used 判断。因为元素可以重复使用所以每层都从头遍历。结果数量是 n 的 k 次方n10、k5 就是十万级n10、k10 直接上百亿。所以这类问题在实际工程里几乎不会真的枚举全部更多是求计数或者配合剪枝。我在做一个活动配置系统时遇到过类似需求一个活动有若干维度渠道、地区、用户等级每个维度有若干取值要生成所有可能的组合做灰度策略。维度少的时候直接枚举没问题维度一多就必须改成按需生成或者用哈希做稀疏存储。这个经验告诉我可重复排列的枚举一定要先估算结果规模。5.2 可重复组合凑硬币与面额问题可重复组合的经典场景是凑硬币、找零钱、面额组合。它和普通组合的区别是递归传i而不是i1允许同一个元素被反复选。def combination_repeat(nums, k): res [] def backtrack(start, path): if len(path) k: res.append(path[:]) return for i in range(start, len(nums)): path.append(nums[i]) backtrack(i, path) path.pop() backtrack(0, []) return res注意backtrack(i, path)里的i不是i1。这一字之差就是可重复和不可重复的分水岭。我建议把这两个模板并排放在一起记写的时候先确认是哪种再决定传 i 还是 i1。5.3 结果规模估算动手前先算一笔账不管是哪种类型动手写代码前先估算结果数量这是我多年养成的习惯。全排列是 n!组合是 C(n,k)可重复排列是 n^k可重复组合是 C(nk-1, k)。这几个公式不用记精确值但要有个量级概念。类型公式n10 时的量级全排列n!约 360 万组合 C(10,5)n!/(k!(n-k)!)252可重复排列n^k (k5)10 万可重复组合C(nk-1,k) (k5)2002看到全排列和可重复排列的量级你就知道为什么这两类问题必须谨慎。实际项目里如果 n 超过 12 还要全排列基本要考虑换算法或者只求计数了。6. 常见问题排查与避坑经验实录6.1 结果重复九成是去重逻辑没写对结果里出现重复项是最常见的问题。排查顺序我一般是这样的先确认数组有没有排序没排序先去重判断必然失效再看去重条件写的是i 0还是i start排列用前者组合用后者最后检查used[i-1]是not used[i-1]还是used[i-1]排列去重用的是not used[i-1]。这三个点任何一个写错都会导致重复。我整理了一个速查表问题现象可能原因修正方法排列结果重复未排序或去重条件错排序 not used[i-1]组合结果重复用了i 0改成i start结果全是空列表path 未拷贝用path[:]结果缺项递归传参错检查 i 与 i16.2 栈溢出递归深度超限排列组合的递归深度等于结果长度全排列 n15 时递归深度就是 15一般不会溢出。但如果你的问题嵌套层数很深比如多维组合就可能触发递归深度限制。Python 默认递归上限是 1000超过会报RecursionError。解决办法有两个一是用sys.setrecursionlimit调高上限但这只是权宜之计二是改写成迭代版本用显式栈模拟递归。我一般优先考虑迭代因为递归深度大的时候即使不报错性能也会受影响。6.3 性能瓶颈剪枝没做到位很多人写完模板发现跑得慢第一反应是Python 太慢其实往往是剪枝没做。组合问题的上界剪枝、组合总和的排序 break、全排列的 used 提前判断这些都是能显著提速的点。我做过一个对比测试n20、k5 的组合问题不剪枝递归调用约 2 万次加上界剪枝后降到 5 千次左右提速接近 4 倍。这个差距在数据量大的时候就是能不能跑完的区别。注意剪枝的前提是数组有序。如果题目给的数组无序先排序再剪枝排序的 O(n log n) 相对于指数级枚举可以忽略不计。6.4 内存爆炸结果集太大当结果数量上百万时把所有结果存进列表会吃掉大量内存。这时候要考虑用生成器yield逐个产出而不是一次性收集。Python 里把res.append改成yield调用方用 for 循环消费内存占用能从 O(结果数) 降到 O(递归深度)。这个技巧在处理大规模枚举时非常实用。我做过一个批量生成配置组合的工具结果有几十万条用列表存直接内存告警改成生成器后平稳运行。7. 从刷题到落地排列组合的实际应用思路排列组合算法在工程里的应用比想象中广。测试用例生成是一个典型场景一个接口有多个参数每个参数有若干取值要覆盖所有组合做测试。这就是可重复排列参数少的时候直接枚举参数多的时候要用正交实验或者成对组合来降维。另一个场景是权限和策略配置。角色、资源、操作三个维度组合出权限点本质上也是排列组合。这时候通常不需要枚举全部而是按需计算某个具体组合是否存在用哈希或者位运算表示比枚举高效得多。还有一类是推荐和匹配。比如给用户推荐商品要从候选池里选 k 个并考虑顺序这就是排列问题。实际系统里当然不会真的枚举所有排列而是用打分排序取 top-k但理解排列的本质有助于你设计打分函数和去重逻辑。我的体会是排列组合的模板要背熟但更重要的是培养先判断类型、再估算规模、最后决定策略的思维习惯。模板解决的是怎么写思维习惯解决的是要不要这么写。后者往往更值钱。最后分享一个我常用的调试技巧写排列组合代码时先用 n3 的小数组手动跑一遍把递归树画出来对照代码看每一步的 path 和 used 状态。小规模验证通过后再上大规模数据能省掉大量盲目调试的时间。这个笨办法我用了很多年至今没找到更好的替代。