字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

思路：

记字符串的长度为n，则有n个位置，对于位置i，字符串里的每个字符都放一次，对于位置i+1，字符串除i位置的字符外，其他都放一次。当到达位置n时，则出现一个满足要求的答案。题目要求不能有重复元素，所以要去重。先把字符串排序，则相同的字符相邻。对于两个相同的字符，如果前一个使用过了，后面一个则不使用。即

vis[j - 1] && s[j - 1] == s[j]

代码:

class Solution {
public:
    vector<string> rec;
    vector<int> vis;

    void backtrack(const string& s, int i, int n, string& perm) {
        if (i == n) {
            rec.push_back(perm);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && vis[j - 1] && s[j - 1] == s[j])) {
                continue;
            }
            vis[j] = true;
            perm.push_back(s[j]);
            backtrack(s, i + 1, n, perm);
            perm.pop_back();
            vis[j] = false;
        }
    }

    vector<string> permutation(string s) {
        int n = s.size();
        vis.resize(n);
        sort(s.begin(), s.end());
        string perm;
        backtrack(s, 0, n, perm);
        return rec;
    }
};