题意

给出一个字符串，求其排列。

思路

该题思路与有重复项数字的全排列类似，只需要将题目中的数字换成字母即可，因此做法也可以采用回溯法，代码如下：

class Solution {
public:
    vector<string > ans;//存储答案用数组
    bool used[10];//判断某个字母是否被使用过
    int N;
  	void dfs(string a,string &str)
    {
        if(a.size()==N){ans.push_back(a);return;}//若求出了一个排列将其存入答案
        for(int i=0;i<N;i++)
        {
            if(!used[i]&& !(i>0 && str[i] == str[i-1] && !used[i-1]))
            {
                used[i]=true;
                a.push_back(str[i]);//放入排列
                dfs(a,str);
                a.pop_back();
                used[i]=false;//回溯
            }
        }
    }
    vector<string> Permutation(string str) {
        memset(used, false, sizeof used);
        N=str.size();
        sort(str.begin(),str.end());
        dfs("",str);//开始搜索
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n!)O(n!)$，为全排列个数。

空间复杂度：$O(n!)O(n!)$，为存储答案所用空间。