class Solution {
public:
    vector<bool> st;    //每个坑的状态，如果坑中有数则ture
    vector<int> path;   //一个可行的输出序列
    vector<vector<int>> res;    //所有可行的排序结果
    vector<vector<int>> permutation(vector<int>& nums) {
        //思路，暴力枚举，首先对每一个数进行排序，使得相同的数在其左右相邻的位置，之后用dfs函数进行递归
        //枚举
        sort(nums.begin(),nums.end());
        st = vector<bool>(nums.size(),false);
        path.resize(nums.size());
        dfs(nums,0,0);
        return res;
    }

    //函数作用是，将初始位置为start的第u个数字进行排序，将可能的结果添加到res中
    void dfs(vector<int>& nums,int u,int start){
        //若当前排序的数字为最后一个数，将结果送到res中并直接返回
        if(u == nums.size()){
            res.push_back(path);
            return;
        }

        //若非最后一个数，对其进行处理
        for(int i = start;i < nums.size();++i)  //注意，并非从start + 1开始因为如果数值不同dfs(nums,u + 1,0)
            if(!st[i]){ //如果该坑位未被占，则处理，否则直接处理下一个坑位
                st[i] = true;
                path[i] = nums[u];
                if(i < nums.size() && nums[u + 1] != nums[u])
                    dfs(nums,u + 1,0);
                else
                    dfs(nums,u + 1,i);
                st[i] = false;
            }
    }
};