题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/

题解

回溯

对给定字符串进行排序，对每一个位置选择一个字符放置，并使用 used 数组确保每个字符只能选一次。

特别的，如果字符串中有相同的字符，比如 “aabc” 中的 “aa”，为方便，我们标记为 “a1a2bc”，可能生成的排列包含 “a1a2bc” 和 “a2a1bc”，但是都为 “aabc”。

这时要保证生成的排列不含重复排列，我们可以生成后再去重（或使用 set），也可以保证这段相同字符的排列唯一，可以规定相同字符必须从左到右排列。比如上面的例子中，无论生成什么排列，我们单独看重复字符 ‘a’ 的排列，都为 “a1a2”，如 “a1a2bc”、“a1ba2c”、“a1bca2”、“ba1a2c”、“ba1ca2”、“bca1a2”。这样就不会因为重复字符的存在而生成重复排列了。

class Solution {
    int n;
    string path;
    vector<string> ans;
    void backtrack(const string& s, vector<bool> used, int i) {
        if (i == n) {
            ans.push_back(path);
            return;
        }
        for (int j = 0; j < n; j++) {
            // 如果该字符与前一个字符相同且前一个字符没选，那么该字符也不能选
            if (used[j] || j > 0 && s[j] == s[j - 1] && !used[j - 1]) continue;
            path.push_back(s[j]); used[j] = true;
            backtrack(s, used, i + 1);
            path.pop_back(); used[j] = false;
        }
    }
public:
    vector<string> permutation(string s) {
        n = s.size();
        sort(s.begin(), s.end());
        vector<bool> used(n, false);
        backtrack(s, used, 0);
        return ans;
    }
};

时间复杂度：O(n×n!)，其中 n 为给定字符串的长度。这些字符的全部排列有 O(n!) 个，每个排列平均需要 O(n) 的时间来生成。

空间复杂度：O(n)。我们需要 O(n) 的栈空间进行回溯，注意返回值不计入空间复杂度。

下一个排列

函数 next_permutation() 已知一个排列，快速得到字典序中的下一个更大的排列。

同样是对字符串排序，获得字典序最小的排列，然后每次获得下一个更大排列，一直到没有更大排列。

C++ 为我们提供了 next_permutation()，当然也可以自己实现它。

class Solution {
    bool next_permutation(string& s) {
        int i = s.size() - 2;
        while (i >= 0 && s[i] >= s[i + 1]) i--;
        if (i >= 0) {
            int j = s.size() - 1;
            while (s[j] <= s[i]) j--;
            swap(s[i], s[j]);
            reverse(s.begin() + i + 1, s.end());
            return true;
        }
        return false;
    }
public:
    vector<string> permutation(string s) {
        sort(s.begin(), s.end());
        vector<string> ans{s};
        // while (::next_permutation(s.begin(), s.end())) ans.push_back(s);
        while (next_permutation(s)) ans.push_back(s);
        return ans;
    }
};