全排列

问题

原题链接：https://leetcode.cn/problems/permutations?envType=study-plan-v2&envId=top-100-liked

解法

这是一个很经典的回溯问题，在学习算法时全排序和八皇后是这类问题的典型。
我们用status记录vector每位数字的状态，已被采用则往下看，否则记录该数字（且修改status位）并递归处理，待长度达标时就完成了一次排列。依次完成全排列。

class Solution {
public:
    int n=0;//记录多次要用的num.size()
    void dfs(vector<int>& nums,vector<bool>& sta,vector<int>& temp,vector<vector<int>>& res){
        //已完成一次全排序
        if(temp.size()==n){
            res.push_back(temp);
            return;
        }
        for(int i=0;i<n;i++){
            if(sta[i]) continue;//若已用，则往后取
            sta[i]=true;
            temp.push_back(nums[i]);
            dfs(nums,sta,temp,res);
            sta[i]=false;
            temp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        n=nums.size();
        vector<bool> sta(n,false);//用以标记nums状态
        vector<int> temp;//暂存结果
        dfs(nums,sta,temp,res);
        return res;
    }
};