leetcode 面試題08.08. 有重複字元串的排列組合

題目描述：

有重複字元串的排列組合。編寫一種方法，計算某字元串的所有排列組合。

示例1:

輸入：S = “qqe”

輸出：[“eqq”,“qeq”,“qqe”]

示例2:

輸入：S = “ab”

輸出：[“ab”, “ba”]

思路：

回溯+剪枝

例如：qeq

首先排序：eqq

剪枝：1、剪去已經周遊過的字元

2、減去一樣的字元

代碼如下：

class Solution {
public:
    int n=0;
    vector<string>res;
    vector<bool>visited;
    string str="";
    vector<string> permutation(string S) {
        if(S.empty()) return {""};
        n=S.size();
        visited=vector(n,false);
        sort(S.begin(),S.end());
        dfs(S,0);
        return res;
    }
    void dfs(string s,int cur){
        if(cur==n){
            res.push_back(str);
            return;
        }
        for(int i=0;i<n;i++){
            if(visited[i]) continue;//剪枝1   
            if(i>0&&s[i]==s[i-1]&&!visited[i-1]) continue;//剪枝2  這裡為什麼還有加一個!visited[i-1]？？
            str+=s[i];
            visited[i]=true;
            dfs(s,cur+1);
            visited[i]=false;
            str.pop_back();
        }
    }
};
           

解釋：