题目描述

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

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

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

$1 <= s 的长度 <= 8$

---

算法

(回溯) $O(n! * n)$

和 46. 全排列 的唯一区别就是这道题目存在重复答案，所以需要去重，去重的思路首先将数组排序，让相同的数相邻，如果当前数等于前一个数且前一个数没有被使用过，则跳过当前数，继续查找下一个要放在当前位置上的数，始终保证排列后的序列相同数的相对顺序不变。

时间复杂度

全排列总共有 $A^n_n$ 种方案，即 $n!$，记录每种方案需要 $O(n)$ 的时间，所以总时间复杂度为 $O(n!*n)$。

空间复杂度

额外空间复杂度 $O(n)$

C++ 代码

class Solution {
public:
    vector<string> res;
    string path;
    vector<bool> st;

    void dfs(int u, string& s) {
        if (u == s.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < s.size(); i ++ ) {
            // 如果当前数等于前一个数且前一个数没用过，则使用前一个数
            if (i && !st[i - 1] && s[i - 1] == s[i]) continue;
            if (!st[i]) {
                path += s[i];
                st[i] = true;
                dfs(u + 1, s);
                st[i] = false;
                path.pop_back();
            }
        }
    }

    vector<string> permutation(string s) {
        sort(s.begin(), s.end());
        st = vector<bool>(s.size());
        dfs(0, s);
        return res;
    }
};