递归法

• 使用flag标记数组表示位置是否被占据
• 排序，判断前一个位置为0且字母相同->相同位置已有该字母出现
• 在上一层递归函数结束后，解除占用

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    void check(vector<string>& vs,vector<int>& flag,string& str,string new_str)
    {
        if(new_str.size()==str.size())
        {
            vs.push_back(new_str);
            return;
        }
        for(int i=0;i<str.size();i++)
        {
            if(flag[i])
            {
                continue;
            }
            //前后字母重复
            if(i>=1&&str[i-1]==str[i]&&!flag[i-1])
            {
                continue;
            }
            flag[i]=1;//被占用
            check(vs,flag,str,new_str+str[i]);
            flag[i]=0;//解除占用
        }
    }
    vector<string> Permutation(string str) {
        // write code here
        vector<string> vs;
        int len=str.size();
        if(!len)
        {
            return vs;
        }
        vector<int> flag(len,0);
        sort(str.begin(),str.end());
        check(vs,flag,str,"");
        return vs;
    }
};