剑指 Offer 38. 字符串的排列（回溯法）

• • 方法一
  • 方法二

class Solution {
public:
    string str;
    int len;
    vector ans;

    void func(int i){
        if(i == len){
            ans.push_back(str);
            return;
        }
        for(int j = i; j < len; j++){
            swap(str[j], str[i]);
            func(i + 1);
            swap(str[j], str[i]);
        }
    }

    vector permutation(string s) {
        // 回溯法
        str = s;
        len = s.size();
        func(0);
        return ans;
    }
};

想着采用排列树的方式解决，可这种方式只能处理字符不重复的字符串

我们这里用set去重，然后构造vector返回即可通过所有测试用例

我们接下来用穷举法解决不可重复问题

完整的解空间树如下（continue）：

注意：从完整的解空间树中可以看到，画红圈的分支不是没有生成，而是由于跳过了重复的字符，所以无法到达最后一层

完整的解空间树如下（break）：

我们避免重复的方法是：最终的排列结果中，保证重复字符的相对位置不变，这就达到了去重的目的

比如： a 1 a 2 a 3 a_1a_2a_3 a1​a2​a3​、 a 1 a 3 a 2 a_1a_3a_2 a1​a3​a2​、 a 2 a 1 a 3 a_2a_1a_3 a2​a1​a3​、 a 2 a 3 a 1 a_2a_3a_1 a2​a3​a1​、 a 3 a 1 a 2 a_3a_1a_2 a3​a1​a2​、 a 3 a 2 a 1 a_3a_2a_1 a3​a2​a1​，我们只保留最后一个

• 准备一个string类型的变量tmp，记录当前选择了哪些字符，深入到解空间树最后一层时，tmp就和原始字符串一样长，可以用ans保存
• 由于需要判断字符是否选择过，还需要一个used数组，判断非第一个重复字符前面的字符是否用过，用过则break，没用过则继续深入下一层

class Solution {
public:
    string str;
    string tmp;
    int len;
    vector used;
    vector ans;

    void func(int i){
        if(i == len){
            ans.push_back(tmp);
        }else{
            for(int j = 0; j < len; j++){
                // 深入一层时，都会遍历所有的字符，如果当前字符被用过，就不会做任何操作
                if(used[j]){
                    continue;
                }
                // 当前字符没用过，但是和前面用过的字符相同（由于排序了，相同的字符一定相邻）
                if(j > 0 && used[j-1] && str[j] == str[j-1]){
                    // 当前字符和前面的相等，且前面的已经用过，则不用当前字符，不在继续向下深入
                    // 也可写成continue
                    break;
                }
                used[j] = true;
                tmp.push_back(str[j]);
                func(i + 1);
                tmp.pop_back();
                used[j] = false;
            }
        }
    }

    vector permutation(string s) {
        // 回溯法
        sort(s.begin(), s.end());
        str = s;
        len = s.size();
        used.assign(len, false);
        func(0);
        return ans;
    }
};