字符串的排列

三种方法；

1. 基于库函数next_permutation(begin, end)
   1. 去重方法：先sort初始字符串再处理（本题初始字符串已经有序）
2. 基于回溯
   1. 通过一个visited数组记录已经被选中的位置
   2. 去重方法：通过set进行去重
3. 基于交换
   1. 去重方法：通过set进行去重

方法一的代码：

//
// Created by jt on 2020/9/18.
//
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if (str.size() < 1) return res;
        do {
            res.push_back(str);
        } while (next_permutation(str.begin(), str.end()));
        return res;
    }
};

方法二的代码：

//
// Created by jt on 2020/9/18.
//
#include <string>
#include <vector>
#include <set>
using namespace std;

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if (str.size() < 1) return res;
        vector<int> visited(str.size(), 0);
        string tmp;
        set<string> st;
        backtrace(st, visited, str, 0, tmp);
        for (auto &a : st) res.push_back(a);
        return res;
    }

    void backtrace(set<string> &st, vector<int> &visited, string &str, int pos, string tmp) {
        if (pos == str.size()) { st.insert(tmp); return; }
        for (int i = 0; i < str.size(); ++i) {
            if (visited[i] == 1) continue;
            else {
                visited[i] = 1;
                tmp.push_back(str[i]);
                backtrace(st, visited, str, pos+1, tmp);
                tmp.pop_back();
                visited[i] = 0;
            }
        }
    }
};

方法三：

//
// Created by jt on 2020/9/18.
//
#include <string>
#include <vector>
#include <set>
using namespace std;

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if (str.size() < 1) return res;
        set<string> st;
        backtrace(st, str, 0);
        for (auto &a : st) res.push_back(a);
        return res;
    }

    void backtrace(set<string> &st, string &str, int pos) {
        if (pos == str.size() - 1) { st.insert(str); return; }
        for (int i = pos; i < str.size(); ++i) {
            if (i != pos && str[i] == str[pos]) continue;
            swap(str[pos], str[i]);
            backtrace(st, str, pos+1);
            swap(str[pos], str[i]);
        }
    }
};