力扣---全排列---回溯

思路：

递归做法，一般会有visit数组来判断第 i 位是否被考虑了。我们先考虑第0位，再考虑第1位，再考虑第2位...dfs函数中还是老套路，先判定特殊条件，再从当下的角度（决定第 j 位是哪个元素），依次遍历visit数组，依次将visit值为0的元素赋给第 j 位，并继续递归（记住要恢复现场）。

代码：

C++：

class Solution {
public:
    void dfs(vector<int>& visit,vector<vector<int>>& res,vector<int>& nums,vector<int>& path,int i,int len){
        if(i==len){
            res.push_back(path);
            return;
        }

        //考虑第i位
        for(int j=0;j<len;j++){
            if(visit[j]==0){
                visit[j]=1;
                path.push_back(nums[j]);
                dfs(visit,res,nums,path,i+1,len);
                visit[j]=0;
                path.pop_back();
            }
        }

    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int len=nums.size();
        vector<int> visit(len,0);
        vector<int> path;
        dfs(visit,res,nums,path,0,len);
        return res;
    }
};

Python：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(visit:List[int],res:List[List[int]],num:List[int],path:List[int],i:int,len_:int):
            if i==len_:
                res.append(path.copy())
                return 
            for j in range(len_):
                if visit[j]==0:
                    visit[j]=1
                    path.append(nums[j])
                    dfs(visit,res,nums,path,i+1,len_)
                    visit[j]=0
                    path.pop()
        res=[]
        len_=len(nums)
        visit=[0]*len_
        path=[]
        dfs(visit,res,nums,path,0,len_)
        return res

注意这句话：

res.append(path.copy())，将 path：List[int] 加入到 res：List[List[int]] 类型中时，记得先将path copy一下，再进行append操作