XingHuiSamaの宝藏之地

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

‍

1. 算法核心思想

本段代码采用了一种基于回溯算法（Backtracking）的深度优先搜索（DFS）策略。其核心目的是计算给定数组中所有元素的不同排列组合。

我在解决本题时，将求解过程具象化为遍历一棵“决策树”。关键难点在于如何清晰地分离“已作出的选择”和“当前可用的剩余选项”。本算法通过动态缩减候选集与引用状态回溯的策略成功实现了这一需求：

隔离候选池（读写分离思路）：不使用额外的高级数据结构（如哈希表或布尔数组）来标记元素是否被使用，而是直接在每一层递归中，利用 vector 的拷贝与 erase 操作，将当前选中的元素从剩余候选池 nums 中物理剔除，确保下一层递归绝不会拿到重复的元素。
共享状态与回溯（状态重置）：通过引用传递 &temp 使得所有递归分支共享同一个路径空间。进入下一层前“推入（push）”元素，从下一层返回后立刻“弹出（pop）”元素，以此撤销当前的选择，恢复到干净的状态，从而去探索下一条岔路。

‍

2. 代码逻辑拆解

第一阶段：数据结构初始化与入口 在主函数 permute 中，初始化了用于存放所有有效排列的二维结果集 res，以及用于记录当前探索路径的一维数组 temp。随后调用辅助函数 func 开启递归搜索。
第二阶段：终止条件判定 (Base Case) 在 func 中，首先判断 nums.size() == 0。若剩余候选池被清空，说明原来的所有数字都已经安全入座，当前的 temp 已经构成了一个完整的全排列。我将其 push_back 收集进 res 中，并直接 return 结束当前深度的探索。
第三阶段：遍历与做选择 通过 for 循环遍历当前层所有的可用候选数字。对于每一个数字 nums[i]：将其放入当前路径：temp.push_back(nums[i])，表示“我在当前位置选择了这个数字”。
第四阶段：刷新剩余选项与深度递归 为了让下一层不再重复选择当前数字，创建了当前候选池的深拷贝 vector<int> temp2 = nums，并利用 erase 方法精确剔除刚刚被选走的数字。随后，携带更新后的剩余池 temp2 和当前路径 temp，调用 func(res, temp2, temp) 潜入下一层。
第五阶段：撤销选择（核心回溯） 当底层的递归执行完毕并返回到当前层时，说明以 nums[i] 为起点的分支已经全探索完了。此时，必须执行 temp.pop_back() 将 nums[i] 移除出路径。这是回溯的灵魂动作——“把吃进去的吐出来”，保证 temp 回到干净状态，以便 for 循环推进到下一个数字进行全新一轮的试探。

‍

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> temp;
        func(res, nums, temp);
        return res;
    }

    void func(vector<vector<int>> &res, vector<int> nums, vector<int> &temp) {
        // 1. 递归终点：没有剩余数字可选时，说明得到了一个完整排列
        if (nums.size() == 0) {
            res.push_back(temp);
            return; 
        }

        // 2. 遍历做选择
        for (int i = 0; i < nums.size(); i++) {
            // 做选择：放入当前元素
            temp.push_back(nums[i]); 
            
            // 刷新剩余选项：拷贝并剔除已选元素
            vector<int> temp2 = nums; 
            temp2.erase(temp2.begin() + i);
            
            // 往下递归，探索下一层
            func(res, temp2, temp); 
            
            // 撤销选择：回溯状态，准备尝试下一个元素
            temp.pop_back(); 
        }
    }
};

3. 复杂度分析

时间复杂度：**** $\mathcal{O}(N \times N!)$

其中 $N$ 为原数组的长度。全排列的总数严格为 $N!$ 种。在每一次得到完整排列并装入结果集时，以及在每一层递归创建局部拷贝 temp2（底层数组拷贝耗时 $\mathcal{O}(N)$ ）时，都会带来线性级别的开销。考虑到决策树的节点总数，总体最坏时间复杂度为 $\mathcal{O}(N \times N!)$ 。
空间复杂度：**** $\mathcal{O}(N^2)$

这里的空间复杂度主要考量的是除最终结果集 res 之外的辅助空间。系统递归调用栈的最大深度为 $N$ 层。在我的这套解法中，每一层递归域内都实例化了一个局部的临时数组 temp2。从顶层到底层，这些临时数组的大小依次为 $N, N-1, N-2, \dots, 1$ 。这些数组同时存在于内存中，其大小总和为一个等差数列求和，因此峰值辅助空间消耗为 $\mathcal{O}(N^2)$ 。

‍