回溯 + 用set去重

class Solution {
  public:
    /*
        原字符串有重复字符, 比如aab
        aab
        aba
        baa
        借用set来进行去重
    */ 
    set<string> result;  
    vector<string> Permutation(string str) {
        if (str.empty()) return vector<string>(result.begin(), result.end());
        
        sort(str.begin(), str.end());
        vector<bool> state(str.size(), false); // 定义state数组, 用于表明是否被选择过
        back_tracking(str, "", state);
        return vector<string>(result.begin(), result.end());
    }

    void back_tracking(string& s, string cur, vector<bool>& state) {
        if (cur.size() == s.size()) {
            result.insert(cur);
            return;
        }
        
        for (int i = 0; i < s.size(); ++i) {
            if (state[i]) continue;
            state[i] = true;
            cur += s[i];   // 加入cur中
            back_tracking(s, cur, state); // 递归
            state[i] = false; // 回溯, state恢复为false
            cur = cur.substr(0, cur.length() - 1); // 回溯, 减掉最后一个字符
        }
        return;
    }
};

回溯 + 不用set去重

class Solution {
  public:
    vector<string> result;  
    vector<string> Permutation(string str) {
        if (str.empty()) return result;
        sort(str.begin(), str.end());
        vector<bool> state(str.size(), false); // 定义state数组, 用于表明是否被选择过
        back_tracking(str, "", state);
        return result;
    }

    void back_tracking(string& s, string cur, vector<bool>& state) {
        if (cur.size() == s.size()) {
            result.push_back(cur);
            return;
        }

        for (int i = 0; i < s.size(); ++i) {
            // 1. 已经被用过
            // 2. 可以用i和i-1判读，因为排序过，遇到重复且前一个被使用则可以跳过
            if (state[i] || (i > 0 && s[i] == s[i-1] && state[i-1])) {
                continue;
            } 
            state[i] = true;
            cur += s[i];   // 加入cur中
            back_tracking(s, cur, state); // 递归
            state[i] = false; // 回溯, state恢复为false
            cur = cur.substr(0, cur.length() - 1); // 回溯, 减掉最后一个字符
        }
        return;
    }
};