★ FEATURED ARTICLE 1. 为什么排列组合值得单独整理成系列排列组合这个主题放在算法题里属于那种“看起来简单、写起来卡壳、面试一问就露馅”的典型。我见过太多人刷了几百道题碰到“全排列去重”“组合总和剪枝”“字典序第k个排列”这类问题还是得从头推。根本原因在于排列组合不是一个单一算法而是一整套思维框架——它涉及递归回溯、状态压缩、剪枝优化、数学推导、去重策略等多个维度每个维度单独拎出来都能写一篇长文。我自己在准备面试和带新人的过程中把排列组合相关的题目系统梳理了一遍发现它们其实可以归成几条清晰的脉络排列问题元素顺序有关、组合问题元素顺序无关、子集问题选或不选、棋盘类问题N皇后、解数独。这四类问题共用同一套回溯模板但各自的剪枝条件、去重逻辑、边界处理完全不同。把这套东西整理清楚基本上覆盖了回溯法80%的面试考点。这篇文章适合谁看如果你正在准备技术面试或者刷题刷到回溯章节觉得混乱又或者你带团队需要一份内部培训材料那这份整理应该能帮你省不少时间。我会从核心思路讲起把每类问题的模板、变体、易错点、优化技巧全部拆开配上可直接运行的代码和详细的执行过程分析。不夸张地说把这篇文章里的内容吃透排列组合类的题目基本可以做到“见题拆题”。2. 排列组合问题的整体分类与核心思路2.1 四类问题的本质区别排列组合问题在算法层面可以分成四个大类它们的核心区别在于“顺序是否重要”和“元素是否可重复使用”。问题类型顺序是否重要元素能否重复使用典型题目排列重要通常不重复全排列、全排列II组合不重要通常不重复组合、组合总和子集不重要不重复子集、子集II棋盘重要不重复N皇后、解数独这个表格看起来简单但实际做题时很多人会混淆。比如“组合总和”里元素可以重复使用但“组合总和II”里每个元素只能用一次——这个区别直接决定了递归时传的是i还是i1。我在下面会逐个拆解。2.2 回溯法的统一模板所有排列组合问题都可以用同一个回溯模板解决区别只在于剪枝条件和去重逻辑。这个模板我称之为“选择-递归-撤销”三步曲def backtrack(路径, 选择列表): if 满足结束条件: 结果集.append(路径.copy()) return for 选择 in 选择列表: 做选择 backtrack(路径, 新的选择列表) 撤销选择这个模板的核心在于在递归之前做选择在递归之后撤销选择。这样做的原因是递归函数返回时路径必须恢复到进入前的状态否则会影响同一层其他分支的遍历。我见过很多初学者忘记撤销导致结果完全错乱。2.3 为什么用回溯而不是其他方法有人会问排列组合能不能用动态规划或者数学公式直接算答案是求数量可以求具体方案不行。比如“全排列有多少种”可以用阶乘算但“列出所有排列”必须用回溯。面试中绝大多数排列组合题要求的是输出所有具体方案所以回溯是首选。另一个常见误区是用多重循环暴力枚举。对于固定层数的问题比如三数之和确实可以但一旦层数不确定比如组合总和循环就写不出来了。回溯的本质是“用递归模拟不确定层数的循环”这是它不可替代的原因。3. 排列问题从全排列到去重与字典序3.1 全排列的基本实现全排列是最基础的排列问题给定一个不含重复数字的数组返回所有可能的排列。比如输入[1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。核心思路是每次从剩余元素中选一个放到当前位置然后递归处理剩下的元素。用代码表示def permute(nums): res [] def backtrack(path, remaining): if not remaining: res.append(path.copy()) return for i in range(len(remaining)): path.append(remaining[i]) backtrack(path, remaining[:i] remaining[i1:]) path.pop() backtrack([], nums) return res这段代码的关键在于remaining[:i] remaining[i1:]——它创建了一个新列表排除了已经选过的元素。这样做的好处是逻辑清晰缺点是每次递归都创建新列表空间开销较大。另一种更常见的写法是用used数组标记def permute(nums): res [] used [False] * len(nums) def backtrack(path): if len(path) len(nums): res.append(path.copy()) 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两种写法时间复杂度都是O(n!)但used数组版本更节省空间也更适合后续扩展去重逻辑。我个人推荐用used数组版本作为标准模板。3.2 全排列II去重的三种策略当数组包含重复元素时比如[1,1,2]直接套用上面的代码会输出重复的排列。去重是排列问题的最大难点我总结了三套方案各有适用场景。方案一用Set去重。最简单粗暴把所有结果放进Set里。缺点是时间复杂度高而且没有利用“剪枝”提前终止无效分支。面试中如果时间紧张可以用但面试官通常会追问“能不能不用额外空间”。方案二排序后剪枝。先对数组排序然后在递归时判断如果当前元素和前一个元素相同且前一个元素没有被使用就跳过。代码如下def permuteUnique(nums): nums.sort() res [] used [False] * len(nums) def backtrack(path): if len(path) len(nums): res.append(path.copy()) 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]的判断会失效因为相同元素可能不相邻。3.3 字典序第k个排列这道题是排列问题的进阶给定n和k返回1到n的第k个排列。如果暴力生成所有排列再取第k个时间复杂度是O(n!)当n9时就会超时。正确做法是逐位确定。核心思路对于n个数字第一位有n种选择每种选择后面跟着(n-1)!个排列。所以可以用k除以(n-1)!来确定第一位是哪个数字然后更新k继续确定第二位。def getPermutation(n, k): factorial [1] * (n 1) for i in range(1, n 1): factorial[i] factorial[i-1] * i nums list(range(1, n 1)) res [] k - 1 for i in range(n, 0, -1): idx k // factorial[i-1] res.append(str(nums.pop(idx))) k % factorial[i-1] return .join(res)这个算法的时间复杂度是O(n^2)因为pop操作是O(n)空间复杂度O(n)。关键在于理解k // factorial[i-1]的含义它表示在当前剩余数字中第idx个数字作为当前位的排列有多少个。这个思路在面试中非常加分因为它展示了数学推导能力。4. 组合问题剪枝与重复使用的边界4.1 组合问题的基本框架组合问题和排列问题的最大区别是组合不关心顺序。比如[1,2]和[2,1]在组合中是同一个结果。这个区别直接体现在递归参数上——组合问题需要传入一个start参数保证每次只从当前元素之后的元素中选择。def combine(n, k): res [] def backtrack(start, path): if len(path) k: res.append(path.copy()) 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)中的i1——它保证下一层递归只从当前元素之后选择从而避免产生[1,2]和[2,1]这样的重复组合。4.2 组合总和元素可重复使用“组合总和”问题中元素可以被重复使用。比如candidates [2,3,6,7]目标值7结果可以是[2,2,3]2用了两次。这时候递归时传的就不是i1而是idef combinationSum(candidates, target): res [] def backtrack(start, path, remaining): if remaining 0: res.append(path.copy()) return if remaining 0: return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i, path, remaining - candidates[i]) path.pop() backtrack(0, [], target) return res这里backtrack(i, ...)允许重复选择当前元素。同时remaining 0的剪枝可以提前终止无效分支。如果先对candidates排序还可以在循环中提前breakcandidates.sort() for i in range(start, len(candidates)): if candidates[i] remaining: break ...这个优化在数据量大时效果明显因为一旦当前元素超过剩余目标值后面的元素更大也不可能满足条件。4.3 组合总和II每个元素只能用一次“组合总和II”的输入数组可能包含重复元素且每个元素只能用一次。这时候需要同时处理两个问题元素不能重复使用传i1和结果不能重复排序后剪枝。def combinationSum2(candidates, target): candidates.sort() res [] def backtrack(start, path, remaining): if remaining 0: res.append(path.copy()) return for i in range(start, len(candidates)): if i start and candidates[i] candidates[i-1]: continue if candidates[i] remaining: break path.append(candidates[i]) backtrack(i 1, path, remaining - candidates[i]) path.pop() backtrack(0, [], target) return res这里i start and candidates[i] candidates[i-1]是去重关键。它的含义是在同一层递归中如果当前元素和前一个元素相同就跳过。注意条件是i start而不是i 0因为start之前的元素是上一层已经选择过的不在当前层的选择范围内。实操心得组合问题的去重条件比排列问题更容易写错。我建议在写代码前先画出递归树标出每一层的选择范围然后判断“同一层重复”和“同一路径重复”的区别。同一层重复用i start同一路径重复用used数组。4.4 电话号码的字母组合这是一道组合问题的变体给定数字字符串返回所有可能的字母组合。比如输入23输出[ad,ae,af,bd,be,bf,cd,ce,cf]。这道题的特殊之处在于每个数字对应的字母数量不同而且组合的“层数”由输入字符串长度决定。解法是标准的回溯def letterCombinations(digits): if not digits: return [] mapping { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz } res [] def backtrack(index, path): if index len(digits): res.append(.join(path)) return for ch in mapping[digits[index]]: path.append(ch) backtrack(index 1, path) path.pop() backtrack(0, []) return res这道题没有剪枝和去重是纯粹的“多叉树遍历”。它的价值在于帮助理解“组合问题的递归深度由输入决定”这个特点。5. 子集问题选或不选的哲学5.1 子集的基本实现子集问题和组合问题的区别在于组合问题要求恰好选k个子集问题要求收集所有可能的子集包括空集。所以子集问题在递归的每一层都要把当前路径加入结果集而不是等到满足某个条件才加入。def subsets(nums): res [] def backtrack(start, path): res.append(path.copy()) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, []) return res注意res.append(path.copy())的位置——它在循环之前保证每个节点都被收集。如果放在循环之后就会漏掉空集和某些中间状态。5.2 子集II去重逻辑当数组包含重复元素时子集问题也需要去重。去重逻辑和组合总和II完全一致def subsetsWithDup(nums): nums.sort() res [] def backtrack(start, path): res.append(path.copy()) 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 res这里的关键还是i start——它保证同一层不选重复元素但不同层可以选相同元素。比如[1,2,2]可以产生[1,2,2]但不会产生两个[1,2]。5.3 递增子序列“递增子序列”是一道特殊的子集问题要求子序列严格递增且不能有重复的子序列。这道题的难点在于不能排序排序会打乱原数组顺序而子序列要求保持相对顺序所以不能用“排序后剪枝”的方法去重。正确做法是用Set记录当前层已经使用过的元素def findSubsequences(nums): res [] def backtrack(start, path): if len(path) 2: res.append(path.copy()) used set() for i in range(start, len(nums)): if nums[i] in used: continue if path and nums[i] path[-1]: continue used.add(nums[i]) path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, []) return res这里used集合是每一层独立的它记录的是“当前层已经选择过的元素值”。因为不能排序所以不能用nums[i] nums[i-1]来判断只能用Set。这个技巧在面试中经常被考察因为它打破了“去重必须排序”的思维定式。注意used集合必须定义在递归函数内部不能定义在外面。如果定义在外面它会跨层记录导致错误剪枝。6. 棋盘类问题N皇后与解数独6.1 N皇后的回溯框架N皇后是排列组合问题的经典应用在n×n棋盘上放置n个皇后要求任意两个皇后不在同一行、同一列、同一对角线。这道题的核心是“逐行放置”每行选一个列位置然后判断是否合法。def solveNQueens(n): res [] board [[.] * n for _ in range(n)] def is_valid(row, col): for i in range(row): if board[i][col] Q: return False for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)): if board[i][j] Q: return False for i, j in zip(range(row-1, -1, -1), range(col1, n)): if board[i][j] Q: return False return True def backtrack(row): if row n: res.append([.join(r) for r in board]) return for col in range(n): if not is_valid(row, col): continue board[row][col] Q backtrack(row 1) board[row][col] . backtrack(0) return resis_valid函数检查三个方向同一列、左上对角线、右上对角线。因为我们是逐行放置的所以不需要检查同一行和下方对角线。6.2 用集合优化合法性判断上面的is_valid函数每次都要遍历时间复杂度是O(n)。可以用三个集合分别记录已占用的列、主对角线、副对角线把判断降到O(1)def solveNQueens(n): res [] cols set() diag1 set() # row - col diag2 set() # row col board [[.] * n for _ in range(n)] def backtrack(row): if row n: res.append([.join(r) for r in board]) return for col in range(n): if col in cols or (row - col) in diag1 or (row col) in diag2: continue cols.add(col) diag1.add(row - col) diag2.add(row col) board[row][col] Q backtrack(row 1) board[row][col] . cols.remove(col) diag1.remove(row - col) diag2.remove(row col) backtrack(0) return res这个优化在n较大时效果显著。主对角线的特征是row - col相同副对角线的特征是row col相同用集合记录可以快速判断。6.3 解数独的回溯实现解数独是二维回溯的典型需要遍历每个空格尝试填入1-9然后判断合法性。难点在于如何高效判断行、列、3×3宫格的合法性。def solveSudoku(board): rows [set() for _ in range(9)] cols [set() for _ in range(9)] boxes [set() for _ in range(9)] for i in range(9): for j in range(9): if board[i][j] ! .: num board[i][j] rows[i].add(num) cols[j].add(num) boxes[(i//3)*3 j//3].add(num) def backtrack(): for i in range(9): for j in range(9): if board[i][j] .: for num in 123456789: box_idx (i//3)*3 j//3 if num in rows[i] or num in cols[j] or num in boxes[box_idx]: continue board[i][j] num rows[i].add(num) cols[j].add(num) boxes[box_idx].add(num) if backtrack(): return True board[i][j] . rows[i].remove(num) cols[j].remove(num) boxes[box_idx].remove(num) return False return True backtrack()这道题的技巧在于用三个集合数组预记录已填数字避免每次判断都遍历。另外backtrack函数返回布尔值一旦找到解就立即返回不再继续搜索。这个“找到即停止”的模式在数独问题中非常重要因为数独只需要一个解。7. 常见问题与排查技巧实录7.1 递归结果重复或遗漏这是排列组合问题最常见的bug。我整理了一个排查表现象可能原因解决方法结果有重复去重条件写错检查i start还是i 0结果遗漏收集时机不对子集问题在循环前收集结果顺序不对递归参数传错组合传i1可重复传i栈溢出递归深度过大检查剪枝条件是否生效7.2 剪枝条件失效剪枝是排列组合问题的性能关键但很容易写错。比如在组合总和中if candidates[i] remaining: break必须配合排序使用。如果没排序就不能用break只能用continue。我见过有人没排序就写break结果漏掉了很多合法组合。另一个常见错误是在去重剪枝中用了i 0而不是i start。这两个条件的区别是i 0会跨层判断导致某些合法分支被错误剪掉。记住同一层去重用i start同一路径去重用used数组。7.3 空间复杂度优化回溯问题的空间复杂度主要来自递归栈和路径存储。有几个优化技巧用path.copy()而不是直接appendpath避免后续修改影响已保存的结果。对于字符串拼接用列表join代替字符串直接相加减少内存分配。在N皇后问题中用集合代替遍历判断把O(n)降到O(1)。实操心得我在面试中遇到过一道题要求输出所有排列但内存限制很严。当时用了used数组原地交换避免了创建新列表顺利通过。原地交换的写法是每次把第i个元素和当前元素交换递归后再换回来。这种写法空间复杂度是O(n)比创建新列表的O(n^2)好很多。7.4 时间复杂度分析排列组合问题的时间复杂度通常是指数级的但不同问题差异很大问题时间复杂度说明全排列O(n!)每个排列都要生成组合O(C(n,k))只生成合法组合子集O(2^n)每个元素选或不选N皇后O(n!)逐行放置剪枝后远小于n!面试中如果面试官问时间复杂度不要只说“指数级”要具体到O(n!)或O(2^n)并解释剪枝对实际运行时间的影响。8. 从刷题到实战的几点体会排列组合这套东西我前后整理了三四遍每次都有新的理解。最开始觉得回溯就是套模板后来发现模板只是骨架真正决定代码质量的是剪枝和去重的细节。再后来带新人发现他们卡住的地方往往不是递归本身而是“什么时候该传i什么时候该传i1”这种边界问题。我的建议是不要死记模板而是画递归树。把每一层的选择范围画出来标出哪些分支是重复的哪些是无效的然后自然就能写出正确的剪枝条件。这个方法看起来笨但比背代码可靠得多。另外排列组合问题在面试中经常和“第k个”“字典序”“内存限制”结合考察的是综合能力。平时练习时不要只满足于AC多想想能不能优化空间、能不能提前终止、能不能用数学方法直接计算。这些思考在面试中比写出代码本身更能体现水平。最后分享一个我常用的调试技巧在递归函数入口打印当前路径和选择范围跑一个小用例观察递归树的展开过程。很多时候代码写错了看一眼输出就知道问题在哪。这个方法比单步调试快得多尤其适合排列组合这种递归层次深的问题。
阅读完成 · 觉得有帮助？
)
