Problem: 46. 全排列
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N * N!)
- 空间复杂度：O(N)
整体思路
这段代码旨在解决一个经典的组合数学问题：全排列 (Permutations)。给定一个不含重复数字的数组 nums，它需要找出其所有可能的全排列，并返回一个包含这些排列的列表。
该算法采用的核心方法是 回溯法（Backtracking），这是一种通过 深度优先搜索（DFS） 来系统地探索所有可能解的搜索策略。
算法的整体思路可以分解为以下步骤：
-
逐位构建排列：
- 算法将生成一个排列的过程看作是逐个“填空”的过程。它定义了一个
dfs(i, ...)函数，其核心任务是确定排列中第i个位置应该填入哪个数字。
- 算法将生成一个排列的过程看作是逐个“填空”的过程。它定义了一个
-
状态维护：
- 为了辅助构建过程，算法使用了两个关键的数据结构：
List<Integer> path：用于存储当前正在构建的排列。boolean[] onPath：一个与原数组nums等长的布尔数组，用作“访问标记”。onPath[j] = true表示nums[j]这个数字已经被放入了当前的path中，不能再被使用。
- 为了辅助构建过程，算法使用了两个关键的数据结构：
-
递归与回溯的核心逻辑：
dfs函数从第 0 位开始 (i=0)。在为第i位选择数字时，它会遍历整个原始数组nums。- 对于
nums中的每一个数字nums[j]，它会检查该数字是否已被使用（if (!onPath[j])）。 - 选择 (Choose)：如果
nums[j]未被使用，就做出选择：
a. 将nums[j]放入当前排列的第i位：path.set(i, nums[j])。
b. 将nums[j]标记为已使用：onPath[j] = true。 - 探索 (Explore)：做出选择后，递归地调用
dfs(i + 1, ...)，去解决下一个子问题——填充第i+1位。 - 撤销选择 (Unchoose / Backtrack)：当对
i+1位的探索（即dfs(i + 1, ...)调用）返回后，必须撤销刚才的选择。这是回溯法的精髓。
a. 将nums[j]标记为未使用：onPath[j] = false。
b. 这样，在下一次循环中，nums[j]就可以被用来填充其他位置，从而形成不同的排列。
-
递归终止条件：
- 当
i的值等于数组长度n时（if (i == n)），意味着排列的所有n个位置都已经被成功填满。 - 此时，一个完整的排列就构建好了（存储在
path中）。 - 将
path的一个深拷贝（new ArrayList<>(path)）添加到最终的结果列表ans中。必须使用拷贝，因为path本身会在回溯过程中被不断修改。
- 当
通过这个“选择-探索-撤销”的循环，算法能够不重不漏地遍历所有可能的排列组合。
完整代码
class Solution {/*** 计算给定数组的全排列。* @param nums 不含重复数字的整数数组* @return 包含所有全排列的列表*/public List<List<Integer>> permute(int[] nums) {int n = nums.length;// ans: 最终的结果列表List<List<Integer>> ans = new ArrayList<>();// path: 用于存储当前正在构建的单个排列路径// Arrays.asList(new Integer[n]) 创建一个固定大小的、由null填充的List，便于后续使用 set 方法List<Integer> path = Arrays.asList(new Integer[n]);// onPath: 标记数组，onPath[j]为true表示nums[j]已在当前path中boolean[] onPath = new boolean[n];// 从第 0 个位置开始进行深度优先搜索dfs(0, nums, ans, path, onPath);return ans;}/*** 深度优先搜索（回溯）辅助函数。* @param i 当前需要填充的排列位置的索引* @param nums 原始输入数组* @param ans 结果列表* @param path 当前构建的排列* @param onPath 标记数组*/private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path, boolean[] onPath) {int n = nums.length;// 递归终止条件：当 i 等于 n 时，说明所有位置都已填满，一个完整的排列已生成if (i == n) {// 将当前路径的一个深拷贝加入到结果列表中// 必须是深拷贝，因为 path 会在回溯过程中被修改ans.add(new ArrayList<>(path));return; // 结束当前递归分支}// 遍历所有可用的数字，尝试将其放入第 i 个位置for (int j = 0; j < n; j++) {// 如果 nums[j] 还未在当前路径中使用过if (!onPath[j]) {// 选择：将 nums[j] 放入第 i 个位置path.set(i, nums[j]);// 标记 nums[j] 为已使用onPath[j] = true;// 探索：递归地去填充下一个位置 (i + 1)dfs(i + 1, nums, ans, path, onPath);// 撤销选择（回溯）：将 nums[j] 标记为未使用，// 这样它就可以在其他分支中被用于其他位置。这是回溯法的核心。onPath[j] = false;}}}
}
时空复杂度
时间复杂度：O(N * N!)
- 排列数量：对于一个包含
N个不同元素的集合，其全排列的数量是N!(N的阶乘)。 - 构建每个排列的成本：
- 算法的搜索过程可以看作是在一棵“排列树”上进行DFS。这棵树有
N!个叶子节点，每个叶子节点代表一个完整的排列。 - 从根节点到任意一个叶子节点的路径长度为
N。 - 当到达一个叶子节点时（即
i == n），需要执行new ArrayList<>(path)操作，这是一个 O(N) 的操作，用于复制当前排列。
- 算法的搜索过程可以看作是在一棵“排列树”上进行DFS。这棵树有
- 综合分析：
- 总的时间复杂度约等于 (叶子节点数量 * 到达叶子节点的成本) + (非叶子节点的计算成本)。
- 非叶子节点的总数也与
N!相关。 - 一个更精确的视角是，总共有
N!个排列，每个排列的生成和复制都需要 O(N) 的时间。因此，总时间复杂度为 O(N * N!)。
空间复杂度：O(N)
- 主要存储开销：我们分析的是额外辅助空间，不包括存储最终结果的
ans列表（否则空间将是 O(N * N!)）。List<Integer> path: 用于存储当前路径，其大小为N。空间复杂度为 O(N)。boolean[] onPath: 标记数组，其大小为N。空间复杂度为 O(N)。- 递归调用栈：
dfs函数的最大递归深度为N（从i=0到i=n）。因此，递归栈所占用的空间为 O(N)。
综合分析：
算法所需的额外辅助空间由 path、onPath 和递归栈深度共同决定。它们都是 O(N) 级别的。因此，总的辅助空间复杂度为 O(N)。
参考灵神
)
