枚举问题的两大利器：深度优先搜索 (DFS) 与下一个排列 (Next Permutation) 算法详解
一、引言：枚举问题的核心挑战
在算法竞赛与工程实践中，暴力枚举常是解决排列/组合问题的兜底方案。然而，当问题规模扩大（如 n > 10）时，直接生成所有排列会导致 O(n!) 时间复杂度，极易超时。此时，DFS 回溯与Next Permutation成为两大高效解法：
- DFS：通过递归 + 剪枝实现灵活枚举，适合需动态过滤的场景
- Next Permutation：原地生成字典序排列，空间高效且常数极小
典型场景：LeetCode 46（全排列）、47（带重复元素的全排列）、31（下一个排列）、60（第 k 个排列）
二、深度优先搜索 (DFS)：回溯法的灵活枚举
1. 核心思想与剪枝机制
DFS 通过递归探索状态空间树，核心逻辑如下：
- 选择：从未使用元素中选一个加入当前路径
- 递归：进入下一层搜索
- 回溯：撤销选择，尝试其他分支
关键优势：剪枝
在递归过程中动态判断是否满足题目约束（如和为特定值、无连续重复等），提前终止无效分支，显著减少搜索空间。
剪枝示例：
题目要求排列中不能有连续偶数
2. 代码实现（含完整注释）
import java.util.*;
public class PermutationDFS {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[nums.length];
dfs(nums, used, path, res);
return res;
}
private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
// 终止条件：路径长度等于数组长度（生成一个完整排列）
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 跳过已选元素（避免重复）
if (used[i]) continue;
// 【剪枝优化】若当前元素与前一个相同且前一个未被使用（处理重复元素）
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
// 1. 选择当前元素
path.add(nums[i]);
used[i] = true;
// 2. 递归下一层
dfs(nums, used, path, res);
// 3. 回溯：撤销选择
path.remove(path.size() - 1);
used[i] = false;
}
}
}
3. 复杂度与适用性
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n!)（需生成所有排列）剪枝可大幅优化（如题目有约束条件） |
| 空间复杂度 | O(n)（递归栈深度 + used 数组 + 路径存储）不含结果集 |
| 适用场景 | ✅ 需动态剪枝的复杂枚举 ✅ 组合/子集问题（非纯排列） ❌ 重复元素需额外处理 |
关键提示：处理重复元素时，必须先排序，并在循环中加入
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])判断。
三、下一个排列 (Next Permutation)：字典序的高效生成
1. 算法原理（核心思想：贪心 + 反转）
算法严格按字典序生成下一个排列，步骤如下（以 [1,2,5,4,3] 为例）：
- 从右向左找第一个降序点
i = 1（nums[1]=2 < nums[2]=5→ 降序点在i=1，因[5,4,3]为降序） - 从右向左找第一个大于
nums[i]的数
j = 3（nums[3]=4 > 2） - 交换
nums[i]与nums[j]→[1,4,5,2,3] - 反转
i后所有元素 →[1,4,2,3,5]（最小字典序）
为什么有效？ 步骤 1：确保
i之后的序列是最大字典序（无法再增大） 步骤 2：找到最小可能增大的数 步骤 4：反转使i后序列最小化（升序）
2. 代码实现（含关键注释）
public class NextPermutation {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2; // 从倒数第二位开始
// 步骤 1：找第一个降序点 (i < i+1)
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = n - 1; // 步骤 2：找第一个大于 nums[i] 的数 (nums[j] > nums[i])
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j); // 步骤 3：交换
}
// 步骤 4：反转 i+1 到末尾（使序列最小化）
reverse(nums, i + 1, n - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start++, end--);
}
}
}
3. 使用流程与复杂度
// 生成全排列示例
Arrays.sort(nums); // 先排序成最小字典序
do {
// 处理当前排列 nums
} while (nextPermutation(nums)); // 直到返回 false（已到最大排列）
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)（单次操作）全排列总时间 O(n·n!)（比 DFS 的 O(n!) 更优） |
| 空间复杂度 | O(1)（原地修改，无需额外空间） |
| 重复元素 | 天然去重（字典序自动跳过重复排列） |
| 适用场景 | ✅ 单纯枚举全排列 ✅ 求第 k 个字典序排列 ✅ 要求空间极小的场景 |
重要特性：
nextPermutation会自动跳过重复排列，无需额外处理（如[1,1,2]会生成[1,2,1]而非重复[1,1,2]）。
四、两种方案的深度对比与选择指南
| 维度 | DFS 回溯 | Next Permutation |
|---|---|---|
| 核心思想 | 递归探索 + 动态剪枝 | 贪心 + 反转（字典序生成） |
| 空间复杂度 | O(n)（需 used 数组 + 递归栈） | O(1)（原地修改） |
| 时间效率 | 依赖剪枝效果（最坏 O(n!)） | 稳定 O(n)/次（常数极小） |
| 重复元素处理 | 需排序 + 额外剪枝（if (i>0 && nums[i]==nums[i-1] && !used[i-1])） | 天然支持（自动去重） |
| 灵活性 | ✅ 极高（可随时加入复杂约束） | ❌ 仅限排列枚举（无法剪枝） |
| 代码可读性 | 逻辑清晰，易理解 | 逻辑精巧，需理解贪心思想 |
| 典型场景 | 1. 需求组合/子集（非纯排列） 2. 动态约束（如和为 K） | 1. 全排列枚举 2. 求第 k 个排列 3. 严格字典序需求 |
选择建议
| 问题特征 | 推荐方案 | 原因 |
|---|---|---|
| 需要剪枝（如组合和为特定值） | DFS | DFS 可灵活加入约束条件，避免无效枚举 |
| 仅需枚举全排列（无额外约束） | Next Permutation | 空间效率高，常数更小，避免递归开销 |
| 有重复元素且需去重 | Next Permutation | 自动处理重复，DFS 需额外排序 + 剪枝 |
| 需求第 k 个字典序排列 | Next Permutation | 直接迭代 k 次即可（DFS 需生成前 k-1 个排列） |
数据规模 n ≤ 10 | DFS 或 Next Permutation | 两者均可，DFS 更易写 |
数据规模 n > 15 | Next Permutation | DFS O(n!) 会超时（15! ≈ 1.3e12 次操作） |
五、结语：掌握工具，精准匹配问题
- DFS 是'瑞士军刀'：
适用于复杂约束的枚举问题（如子集和、路径规划），灵活性是其核心价值。当数据量小（n ≤ 10）或需动态剪枝时，DFS 是首选。 - Next Permutation 是'高效引擎'：
适用于纯字典序枚举场景，空间效率与时间常数优势显著。在n > 12时，其O(n)/次 的特性可避免 DFS 的O(n!)瓶颈。
终极建议：遇到排列问题，先判断是否需要剪枝 → 需剪枝选 DFS，否则选 Next Permutation。重复元素问题 → 优先选 Next Permutation（避免 DFS 的去重逻辑）。生成全排列时，Next Permutation 比 DFS 快 2-3 倍（实测
n=15时）
