题目描述

输入一组数字（可能包含重复数字），输出其所有的排列方式。

感受

先利用深度优先搜索排出所有的索引，然后去重，去重时注意erase方法删除元素后，所有元素索引都会向前，此时可以跳过这个循环，内循环的索引不更新

class Solution {
public:
    bool path[11];
    vector<vector<int>> resnum;

    void dfs(int n,int u,bool path[],vector<int>& temp){
        if(u==n){
            resnum.push_back(temp);
        }else{
            for(int i=0;i<n;i++){
                if(!path[i]){
                    path[i]=true;
                    temp[u]=i;
                    dfs(n,u+1,path,temp);
                    path[i]=false;
                }
            }
        }
    }

    vector<vector<int>> permutation(vector<int>& nums) {
        vector<int> temp(nums.size());
        vector<vector<int>> ansnum;
        dfs(nums.size(),0,path,temp);

        for(int i=0;i<resnum.size();i++){
            vector<int> tempc(nums.size());
            for(int j=0;j<nums.size();j++){
                tempc[j]=nums[resnum[i][j]];
            }
            ansnum.push_back(tempc);
        }

        int i=0,j=1;
        while(i<ansnum.size()){
            j=i+1;
            while(j<ansnum.size()){
                if(ansnum[i]==ansnum[j]){
                    ansnum.erase(ansnum.begin()+j);
                    continue;
                }
                j++;
            }
            i++;
        }

        return ansnum;
    }
};