题解 | #字符串的排列#

#include <vector>
class Solution {
public:
    void dfs(int n, string temp, vector<string> & ans, vector<bool> vis,string str){
        if(temp.size() == n) ans.push_back(temp);
        for(int i = 0; i < n; i++){
            if(vis[i] == false) {
                if(i == 0){
                    vis[i] = true;
                    dfs(n, temp + str[i], ans, vis, str);
                    vis[i] = false;
                }
                else{
                    if(str[i] == str[i - 1] && vis[i - 1] == false) continue;
                    else {
                        vis[i] = true;
                        dfs(n, temp + str[i], ans, vis, str);
                        vis[i] = false;
                    }
                }
            }

    }
    }
    vector<string> Permutation(string str) {
        //首先要用到回溯，终止条件就是长度等于字符串长度，
        //其次，要去重就要一个访问数组，对于那种自己准备访问但是前面字符与自己相同且此次未被访问的得直接跳过
        int n = str.size();
        sort(str.begin(), str.end());
        string temp;
        vector<string>ans;
        vector<bool> vis(n, false);
        dfs(n, temp, ans, vis, str);
        return ans;
    }
};