题解 | #字符串的排列#

#include <vector>
class Solution {
public:

 //感觉是递归类的题目，回溯？ 怎么回溯,重点是怎么跳过重复的排列
    vector<string> Permutation(string str) {
        int n = str.size();
        vector<string> ans;
        sort(str.begin(), str.end());
        if(n == 0) return ans;
        if(n == 1) return {str};
        vector<bool> vis(n,false);
        string temp;
        dfs(str, vis, temp, n, ans);
        return ans;
    }
    void dfs(string & str, vector<bool> vis, string temp, int n, vector<string> &ans){
        if(temp.size() == n) ans.push_back(temp);
        for(int i = 0; i < n; i++){
            if(i != 0 && vis[i - 1] == false && str[i] == str[i - 1] ) continue; //避免重复的情况
            if(vis[i] == false ) {
                temp += str[i];
               
                vis[i] = true;
                dfs(str, vis, temp, n, ans);
                temp.pop_back(); //这个相当于进行回溯
                vis[i] = false;
                
            }
            
        }
    }
};