題目：有重復字符串的排列組合
輸入：S = "qqe"
輸出：["eqq","qeq","qqe"]示例2：
輸入：S = "ab"
輸出：["ab", "ba"]提示:
字符都是英文字母。
字符串長度在[1, 9]之間。
分析
和昨天那道”無重復字符串的排列組合”類似，區別在于這道題的輸入字符串中有重復的字符，還是使用回溯思想，回溯前先將字符串排好序，這樣相同的字符位置就會是連續的，在循環遍歷的時候判斷一下字符是否重復，跳過重復字符即可，注意如果當前字符和上一字符相同，需要判斷上一字符是否使用過，如果使用過則繼續，沒有使用過則跳過，這里可以選擇時候可以選擇使用過的跳過，也可以選擇未使用過的跳過，都可以，只是一定要兩者選其一。
代碼
class Solution {
public:
vector<string> permutation(string S) {
sort(S.begin(), S.end());
string path;
used.resize(S.size(), false);
dfs(S, path);
return ret;
}
vector<string> ret;
vector<bool> used;
void dfs(string& S, string& path) {
if (path.size() == S.size()) {
ret.push_back(path);
return;
}
for (int i = 0, size = S.size(); i < size; ++i) {
if (i > 0 && S[i] == S[i-1] && !used[i-1]) continue;
// if (i > 0 && S[i] == S[i-1] && used[i-1]) continue;也可以
if (used[i]) continue;
used[i] = true;
path.push_back(S[i]);
dfs(S, path);
used[i] = false;
path.pop_back();
}
}
};
代碼精進之路
代碼精進之路，我們一起成長！