引言 (Introduction)
上一篇文章中，我们建立了回溯算法的通用模板，并以子集生成问题完成了初步实践。子集问题关心的是"每个元素选或不选"，而排列与组合问题关心的则是"从 $n$ 个元素中选出 $k$ 个，按特定规则排列"。这三者构成了回溯算法最基础的三大变体。
本文是本系列第二篇，聚焦于排列（Permutation）与组合（Combination）问题。我们将揭示 start 参数在不同问题中的语义差异，建立"有重元素去重"的统一思维框架，并通过组合总和类问题理解纵向剪枝（按值剪枝）的实际应用。
1. 排列 vs 组合：start 参数的语义
1.1 核心区别
子集、组合、排列三者的递归结构差异，全部凝聚在是否使用 start 参数以及如何传递 start 这一点上：
| 问题类型 | start 参数 |
递归调用传入 | 语义 |
|---|---|---|---|
| 子集 | 需要 | i + 1 |
每个元素只能用一次，不计顺序 |
| 组合 | 需要 | i + 1（无重）/ i（可重） |
选 $k$ 个元素，不计顺序 |
| 排列 | 不需要 | —（每次从 0 开始） | 计顺序，所有元素都可选（除已选过的） |
直觉解释：
- 组合的
[1, 2]和[2, 1]被视为同一个结果 → 需要start来强制"只向后选"，人为排除不同顺序。 - 排列的
[1, 2]和[2, 1]被视为两个不同结果 → 不需要start，但需要used数组确保同一元素不被重复选中。
1.2 排列的递归结构
以 nums = [1, 2, 3] 的全排列为例：
[ ]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
每一层的 for 循环都从 $0$ 开始遍历，依靠 used[i] 跳过已经在 path 中的元素。这与子集/组合的"从 start 开始"形成鲜明对比。
2. LeetCode 46 & 47：全排列（Permutations）
2.1 LeetCode 46：无重复元素的全排列
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res: List[List[int]] = []
path: List[int] = []
used: List[bool] = [False] * len(nums)
def dfs() -> None:
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]: # 跳过已在 path 中的元素
continue
used[i] = True
path.append(nums[i])
dfs()
path.pop() # 回溯
used[i] = False # 回溯
dfs()
return res
递归树的可视化（每一层从 $0$ 扫描，跳过 used=True 的元素）：
dfs(0): i=0 → used[0]=T, path=[1]
dfs(1): i=0(used), i=1 → used[1]=T, path=[1,2]
dfs(2): i=0(used), i=1(used), i=2 → used[2]=T, path=[1,2,3]
dfs(3): len(path)==3 → 记录 [1,2,3], return
back: path=[1,2], used[2]=F
dfs(2): i=2 done, return
back: path=[1], used[1]=F
dfs(1): i=2 → used[2]=T, path=[1,3]
...
时间复杂度：$O(N \cdot N!)$。排列共有 $N!$ 个，每个排列的拷贝成本为 $O(N)$。
2.2 LeetCode 47：含重复元素的全排列
当 nums = [1, 1, 2] 时，两个相同的 1 交换位置会产生相同的排列（例如第一个 1 在第二个 1 左面 vs 右面）。去重需要排序 + 横向剪枝：
from typing import List
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res: List[List[int]] = []
path: List[int] = []
used: List[bool] = [False] * len(nums)
def dfs() -> None:
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# 横向剪枝：同一层跳过重复元素
# 条件解释：nums[i]==nums[i-1] 且前一个相同元素未被使用
# 说明前一个相同元素的排列已经被上一轮循环完全枚举过了
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] 是正确的剪枝条件？
设 nums = [1_a, 1_b, 2]（$1_a$ 和 $1_b$ 值相同但索引不同）。当 i = 1（指向 $1_b$）时：
- 如果
used[0]为False（$1_a$ 未被选），说明当前排列还没有包含 $1_a$。此时如果选了 $1_b$ 放到当前位置，它产生的所有排列都已经在上一轮循环（当 $1_a$ 放在这个位置时）被完整枚举过了。所以可以跳过。 - 如果
used[0]为True（$1_a$ 已经在 path 中），说明当前排列已经选了 $1_a$，此时选 $1_b$ 放在不同位置是合理的——[1_a, 1_b, 2]和[1_a, 2, 1_b]是两个不同的排列。所以不能跳过。
记忆技巧：排列去重用
used[i-1] == False（前一个相同元素未被选），子集/组合去重用i > start。两者的本质是一回事——都是"同一层不选重复兄弟节点"。排列中没有start参数，所以用used数组来表征"同一层"。
3. LeetCode 77：组合（Combinations）
3.1 无重复组合
组合问题是子集问题的"定长版本"：给定 $1$ 到 $n$ 的整数，选出 $k$ 个数的所有组合。
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res: List[List[int]] = []
path: List[int] = []
def dfs(start: int) -> None:
# 到达叶节点（恰好 k 个元素）才记录
if len(path) == k:
res.append(path[:])
return
# 纵向剪枝：如果剩余可选元素不足以凑齐 k 个，提前终止
# 还需 need = k - len(path) 个元素
# 剩余可选 = n - i + 1（i 从 start 开始）
# 需要满足：n - i + 1 >= need → i <= n - need + 1
need = k - len(path)
for i in range(start, n - need + 2):
path.append(i)
dfs(i + 1)
path.pop()
dfs(1)
return res
纵向剪枝分析：
在 n = 5, k = 3 的例子里，当 path = [4] 时还需再选 $2$ 个元素，但从 $5$ 开始只剩 $1$ 个可选，无论如何凑不够 $3$ 个。i <= n - need + 1 这个条件精确排除了这类"必死"的分支：
这是回溯算法中最经典的值无关纵向剪枝——仅根据剩余数量做减法。
3.2 组合与子集的关系
组合 = 子集 + 长度限制。两种写法：
# 写法1：子集 + 长度过滤
def dfs(start: int) -> None:
if len(path) == k:
res.append(path[:])
return
# 但这也意味着 len(path) < k 的非叶节点也会被记录（如果使用子集模板）
# 写法2：专用的组合模板（推荐）
def dfs(start: int) -> None:
if len(path) == k:
res.append(path[:])
return
for i in range(start, n + 1):
path.append(i)
dfs(i + 1)
path.pop()
推荐专用模板——语义清晰，剪枝条件可以独立优化。
4. LeetCode 39 & 40：组合总和
组合总和问题引入了元素可重复使用和按总和纵向剪枝两种新变量。
4.1 LeetCode 39：组合总和（元素可无限复用）
题目：给定一个无重复元素的数组 candidates 和一个目标数 target，找出所有和为 target 的组合。每个元素可以被无限次选取。
与普通组合的区别：同一个数字可以被选多次 → 递归调用时 start 传 i（而非 i + 1）。
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort() # 排序使纵向剪枝生效
res: List[List[int]] = []
path: List[int] = []
def dfs(start: int, remaining: int) -> None:
if remaining == 0:
res.append(path[:])
return
if remaining < 0: # 超过 target，终止
return
for i in range(start, len(candidates)):
# 纵向剪枝：如果当前元素已经超过剩余值，后面的更大元素也不可能
if candidates[i] > remaining:
break
path.append(candidates[i])
dfs(i, remaining - candidates[i]) # 传 i，允许重复使用
path.pop()
dfs(0, target)
return res
关键点：
dfs(i, ...)vsdfs(i + 1, ...)：传i表示当前元素可重复使用；传i + 1表示不可重复。- 排序 +
if cand > remaining: break：利用升序性质进行按值的纵向剪枝，直接把 DFS 树砍掉一半。
4.2 LeetCode 40：组合总和 II（每个元素只能用一次）
题目：与 39 相同，但 candidates 中的每个数字只能被使用一次，且 candidates 可能包含重复数字。
这道题同时需要横向去重（子集 II 的技巧）和纵向剪枝（组合总和的技巧）：
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res: List[List[int]] = []
path: List[int] = []
def dfs(start: int, remaining: int) -> None:
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
# 纵向剪枝：超了
if candidates[i] > remaining:
break
# 横向剪枝：同一层跳过重复元素
if i > start and candidates[i] == candidates[i - 1]:
continue
path.append(candidates[i])
dfs(i + 1, remaining - candidates[i]) # 传 i+1，不可重复使用
path.pop()
dfs(0, target)
return res
三种剪枝的叠用：
candidates = [1, 1, 2, 5, 6], target = 8
dfs(0, 8)
/ | \
1 1(×) 2 ← 横向剪枝：第二个1被跳过
/ | \ ... / | \
1 2 5 2 5 6 ← 纵向剪枝：6 > remaining(6)? 不，6=6
/| | | |
... ... ... ...
5. 去重策略对比总结
排列去重和组合去重容易混淆，这里给出明确对比：
| 特征 | 子集 / 组合去重 | 排列去重 |
|---|---|---|
| 前提 | 排序 | 排序 |
| 剪枝条件 | i > start and nums[i] == nums[i-1] |
i > 0 and nums[i] == nums[i-1] and not used[i-1] |
| 依赖变量 | start（隐式标记"同一层"） |
used 数组（显式标记已选/未选） |
| 剪枝范围 | 横向（同层跳过相同兄弟） | 横向（同层跳过相同兄弟） |
| 核心直觉 | 同一层中，重复元素的第一个实例已经枚举了所有以该值为起点的组合 | 同一层中，重复元素的第一个未使用实例已经生成了所有以该值填入当前位置的排列 |
记忆口诀：组合看 start，排列看 used。排列 dedup 记 not used[i-1]；组合 dedup 记 i > start。
结论 (Conclusion)
本文系统辨析了回溯算法中排列与组合的递归结构差异，核心认识可以归纳为一句话：start 参数的有无决定了"顺序是否被考虑"，used 数组的引入为排列提供了去重所需的状态标记。
要点回顾：
- 排列无需
start，每次从 0 遍历；依赖used数组避免元素重复使用。 - 组合需要
start，且i + 1vsi的传参差异决定了元素能否重复使用。 - 两种剪枝层次：横向剪枝（
i > start/not used[i-1]）处理重复元素，纵向剪枝（remaining < cand、i <= n - need + 1）提前终止必死分支。 - 组合总和是组合模板 + 按值纵向剪枝，39（元素无限）与 40（元素有限）的区别仅在于
start传参与否和是否需要横向去重。
下一篇我们将进入分割与棋盘问题——这类问题将回溯的"状态定义"从列表推进到更复杂的结构（切割线、棋盘坐标），并引入多状态标记技巧。