1. 为什么排列组合值得单独整理成系列
排列组合这个主题，放在算法题里属于那种“看起来简单、写起来卡壳、面试一问就露馅”的典型。我见过太多人刷了几百道题，碰到“全排列去重”“组合总和剪枝”“字典序第k个排列”这类问题还是得从头推。根本原因在于，排列组合不是一个单一算法，而是一整套思维框架——它涉及递归回溯、状态压缩、剪枝优化、数学推导、去重策略等多个维度，每个维度单独拎出来都能写一篇长文。
我自己在准备面试和带新人的过程中，把排列组合相关的题目系统梳理了一遍，发现它们其实可以归成几条清晰的脉络：排列问题（元素顺序有关）、组合问题（元素顺序无关）、子集问题（选或不选）、棋盘类问题（N皇后、解数独）。这四类问题共用同一套回溯模板，但各自的剪枝条件、去重逻辑、边界处理完全不同。把这套东西整理清楚，基本上覆盖了回溯法80%的面试考点。
这篇文章适合谁看？如果你正在准备技术面试，或者刷题刷到回溯章节觉得混乱，又或者你带团队需要一份内部培训材料，那这份整理应该能帮你省不少时间。我会从核心思路讲起，把每类问题的模板、变体、易错点、优化技巧全部拆开，配上可直接运行的代码和详细的执行过程分析。不夸张地说，把这篇文章里的内容吃透，排列组合类的题目基本可以做到“见题拆题”。
2. 排列组合问题的整体分类与核心思路
2.1 四类问题的本质区别
排列组合问题在算法层面可以分成四个大类，它们的核心区别在于“顺序是否重要”和“元素是否可重复使用”。
| 问题类型 | 顺序是否重要 | 元素能否重复使用 | 典型题目 |
|---|---|---|---|
| 排列 | 重要 | 通常不重复 | 全排列、全排列II |
| 组合 | 不重要 | 通常不重复 | 组合、组合总和 |
| 子集 | 不重要 | 不重复 | 子集、子集II |
| 棋盘 | 重要 | 不重复 | N皇后、解数独 |
这个表格看起来简单，但实际做题时很多人会混淆。比如“组合总和”里元素可以重复使用，但“组合总和II”里每个元素只能用一次——这个区别直接决定了递归时传的是i还是i+1。我在下面会逐个拆解。
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[i+1:]) path.pop() backtrack([], nums) return res这段代码的关键在于remaining[:i] + remaining[i+1:]——它创建了一个新列表，排除了已经选过的元素。这样做的好处是逻辑清晰，缺点是每次递归都创建新列表，空间开销较大。另一种更常见的写法是用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!)，当n=9时就会超时。正确做法是逐位确定。
核心思路：对于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)中的i+1——它保证下一层递归只从当前元素之后选择，从而避免产生[1,2]和[2,1]这样的重复组合。
4.2 组合总和：元素可重复使用
“组合总和”问题中，元素可以被重复使用。比如candidates = [2,3,6,7]，目标值7，结果可以是[2,2,3]（2用了两次）。这时候递归时传的就不是i+1，而是i：
def 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排序，还可以在循环中提前break：
candidates.sort() for i in range(start, len(candidates)): if candidates[i] > remaining: break ...这个优化在数据量大时效果明显，因为一旦当前元素超过剩余目标值，后面的元素更大，也不可能满足条件。
4.3 组合总和II：每个元素只能用一次
“组合总和II”的输入数组可能包含重复元素，且每个元素只能用一次。这时候需要同时处理两个问题：元素不能重复使用（传i+1）和结果不能重复（排序后剪枝）。
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(col+1, 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 |
| 结果遗漏 | 收集时机不对 | 子集问题在循环前收集 |
| 结果顺序不对 | 递归参数传错 | 组合传i+1，可重复传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，什么时候该传i+1”这种边界问题。
我的建议是：不要死记模板，而是画递归树。把每一层的选择范围画出来，标出哪些分支是重复的，哪些是无效的，然后自然就能写出正确的剪枝条件。这个方法看起来笨，但比背代码可靠得多。
另外，排列组合问题在面试中经常和“第k个”“字典序”“内存限制”结合，考察的是综合能力。平时练习时不要只满足于AC，多想想能不能优化空间、能不能提前终止、能不能用数学方法直接计算。这些思考在面试中比写出代码本身更能体现水平。
最后分享一个我常用的调试技巧：在递归函数入口打印当前路径和选择范围，跑一个小用例，观察递归树的展开过程。很多时候代码写错了，看一眼输出就知道问题在哪。这个方法比单步调试快得多，尤其适合排列组合这种递归层次深的问题。
