前言

太久没刷leetcode了。竟然有些忘记。
看了题解才记起来这个一定要用dfs，思想是用给定的数填空，一步步填上即可，每步是dfs的一层就是了。

第一反应就是python

py里面有这个工具可以直接生成permutation

def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

然而我是不会用py偷懒的！嗯！

naive：map记录是否用掉那个数

暴力dfs：

class Solution {
public:
    map<int,bool> is_used;
    void fillblank(vector<vector<int>>& res,vector<int> nums,vector<int>& working_array,int step,int stop){
        if(step==stop){
            res.emplace_back(working_array);
            return;
        }
        for(int i=0;i<stop;i++){
            if(is_used[nums[i]]) continue;
            // do it
            working_array.emplace_back(nums[i]);
            is_used[nums[i]]=true;
            fillblank(res,nums,working_array,step+1,stop);
            // undo it
            working_array.pop_back();
            is_used[nums[i]]=false;
        }
        
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> working_array;
        fillblank(res, nums, working_array,0, (int)nums.size());
        return res;
    }
};

ac是ac了，见笑了各位。

省空间方法

何必要用is_used呢？
题解给了一个省掉记录是否遍历过的方法。

我们可以将题目给定的数组划分左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。

那虽然这样说是省空间，但是理解起来有点费劲。
之前标记是否访问过，是直接用map，但是现在变成了swap，因为我把你换到左边，就是你已经访问过嘛，把你换到右边，就是你还没访问过。
所以do、undo都变成了swap而不是对is_used进行操作了。
另外，step作为标记递归深度的变量，他标记了我目前要添加哪个数（的index），同时也做了boundary的角色，swap之后，boundary左侧的数字都被访问过了，右侧的都没有被访问。
那么对于没访问过的点，我管你是在哪里的点，统统给我继续dfs，你看里面那个for循环，只需循环右侧那些没访问过的点就可以了。

class Solution {
public:
    void fillblank(vector<vector<int>>& res, vector<int>& nums,vector<int> working_array, int step, int stop){
        if(step==stop){
            res.emplace_back(working_array);
        }
        for(int i=step;i<stop;i++){
            // do 
            working_array.emplace_back(nums[step]);
            swap(nums[i],nums[step]);
            fillblank(res,nums,working_array,step+1,stop);
            // undo
            working_array.pop_back();
            swap(nums[i],nums[step]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> working_array;
        fillblank(res,nums,working_array,0,nums.size());
        return res;
    }
};

我还想再省空间……

蛋蛋，我看了下题解，他连working_array这个东西都省了，原因是啥？因为swap本身就在nums中进行啊！本身swap之后的nums就是working_array啊！何必再多一个working array呢？
总之，更多的空间上的冗余，可读性更高些；要省空间，那么就得多费脑子咯！
改进后：

class Solution {
public:
    void fillblank(vector<vector<int>>& res, vector<int> working_array, int step, int stop){
        if(step==stop){
            res.emplace_back(working_array);
        }
        for(int i=step;i<stop;i++){
            // do 
            swap(working_array[i],working_array[step]);
            fillblank(res,working_array,step+1,stop);
            // undo
            swap(working_array[i],working_array[step]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        fillblank(res,nums,0,nums.size());
        return res;
    }
};

附一张ac图

三次分别是三次改进。