解法一：回溯 + set

利用回溯方法进行求解的思路如下：（具体递归过程见图示）

1. 对于每一个位置，都有「选」和「不选」两种可能，因此需要定义一个state数组用来记录「当前元素是否已经被选择」；
2. 字符串cur用来记录「当前」字符串的情况，在每次递归时，在cur末尾加上当前字符（若其未被选择过），然后进入下一次递归；当cur字符串与原字符串长度相同时，即说明已经完成「整个字符串的排列」，因此将其添加至结果中；
3. 此外，在每次递归时，需要将该字符的state数组置位true，说明其已经被选择了；在递归完成后，需要「恢复现场」：把该字符的state数组置位false，并将其从cur中去掉；
4. 每次递归过程都从0开始（与这题不同），这是因为：尽管已经递归到后面的元素了，但前面的元素仍然需要有「被选择」的机会，例如：在字符串”abc“中，当字符c被加入到cur中时，字符a和字符b仍然需要有「被选择」的机会，因此每次递归都需要从0位置开始。
5. 由于原字符串会出现重复字符，因此需要用set数据结构完成去重工作。

基于上述思路，实现的代码如下：

class Solution {
public:
    set<string> res; 
    vector<string> Permutation(string str) {
        if (str.empty()) 
            return vector<string>(res.begin(), res.end()); 
          sort(str.begin(), str.end()); // 排序
        vector<bool> state(str.size(), false); // 定义state数组，原来表明是否已经被选择过
        backtracking(str, "", state); // 调用递归函数
        return vector<string>(res.begin(), res.end());  
    }
    void backtracking(string s, string cur, vector<bool> &state) {
        if (cur.size() == s.size()) { // 遍历到末尾
            res.insert(cur); // 存储结果
            return; 
        }
        for (int i = 0; i < s.size(); i ++) { //每一次递归都从0位置开始遍历 
            if (state[i]) // 已经被使用了，跳过
                continue; 
            state[i] = true; // 置为true，代表使用它
            cur += s[i]; // 加到cur中
            backtracking(s, cur, state); // 下一次递归
            state[i] = false; // 恢复现场
            cur = cur.substr(0, cur.length() - 1); // 去掉最后一个字符
        }
    }
};

设数组的长度为N，则（最坏情况下，即无重复）全排列共有N!种，因此共需要调用递归函数次。此外，在每次递归时，set（底层实现为红黑树）插入数据的平均时间复杂度为，但每次递归需要完成for循环（最坏时间复杂度为），且保存结果需要时间复杂度，而，故总时间复杂度为；

该方法递归使用栈空间，空间复杂度为。

解法二：回溯 + 不需要set

解法一使用set进行去重，但其在去重前会获得许多重复的结果。这一解法可以进一步优化：在递归的过程中即完成去重的工作。

思路如下：

在进行每次递归时，如果当前元素与前一元素相同，且前一元素已经被使用过了，则无需再对当前元素进行递归，具体过程见图示。
（为更好地表示重复元素，图中将两个b字符分别表示为b1、b2）

实现的代码如下：

class Solution {
public:
    vector<string> res; 
    vector<string> Permutation(string str) {
        if (str.empty()) 
            return res; 
        sort(str.begin(), str.end()); 
        vector<bool> state(str.size(), false); // 定义state数组，原来表明是否已经被选择过
        backtracking(str, "", state); // 调用递归函数
        return res;  
    }
    void backtracking(string s, string cur, vector<bool> &state) {
        if (cur.size() == s.size()) { // 遍历到末尾
            res.push_back(cur); // 存储结果
            return; 
        }
        for (int i = 0; i < s.size(); i ++) { //每一次递归都从0位置开始遍历 
            if (state[i] || (i > 0 && s[i] == s[i - 1] && state[i - 1])) // 已经被使用了，跳过；或是遇到重复，并且前一个重复元素已经被使用过了，跳过
                continue; 
            state[i] = true; // 置为true，代表使用它
            cur += s[i]; // 加到cur中
            backtracking(s, cur, state); // 下一次递归
            state[i] = false; // 恢复现场
            cur = cur.substr(0, cur.length() - 1); // 去掉最后一个字符
        }
    }
};

该方法在最坏情况下时间复杂度与解法一相同，为，但当出现重复时，解法二不需要「求出所有的重复组合之后再去重」，因此相对于解法一而言，优化了时间复杂度；

与解法一同理，该方法空间复杂度为。