> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/lcof/mian-shi-ti-38.md).

# 面试题38

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

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

```
示例:

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

## 限制：

* 1 <= s 的长度 <= 8

## Solutions

1. **backtrack with counter**

```cpp
class Solution {
public:
    vector<string> res;
    vector<int> m;
    string curs;

    void dfs(string & s) {
        if (curs.size() == s.size())
            res.push_back(curs);
        else {
            for (int c = 0; c < 26; c++) {
                if (m[c] <= 0)
                    continue;
                m[c]--;
                curs.push_back('a' + c);
                dfs(s);
                curs.pop_back();
                m[c]++;
            }
        }
    }
    vector<string> permutation(string s) {
        m =  vector<int>(26);
        for (auto & c : s)
            m[c - 'a']++;
        dfs(s);

        return res;
    }
};
```

1. **backtrack with swap**
2. In each recursive call, using numbers(characters) with the same value are forbidden.
3. Since swap could break the continuousness of two numbers, additional steps are required for checking duplicates.

```cpp
class Solution {
public:
    vector<string> res;

    void dfs(string & s, int st) {
        if (st == s.size()) {
            res.push_back(s);
            return;
        }
        int seen = 0;
        for (int i = st; i < s.size(); i++) {
            if (seen & (1 << (s[i] - 'a')))
                continue;
            seen |= (1 << (s[i] - 'a'));
            swap(s[st], s[i]);
            dfs(s, st + 1);
            // since we are passing reference, this pair of characters needs to be restored.
            swap(s[st], s[i]);
        }
    }
    vector<string> permutation(string s) {
        dfs(s, 0);
        return res;
    }
};
```

* Or another version based on sorted string, we always choose to swap the current character with the inserted character(first) and do not swap back.
* For example:
  * `aabbcc`, when the insertion position is `0`, there are `3` possible strings.
  * `aabbcc`
  * `baabcc`
  * `caabbc`
  * The ordering of each pair of character doesn't change after the swap operation which is different from that in the previous solution.

```cpp
class Solution {
public:
    vector<string> res;

    void dfs(string s, int st) {
        if (st == s.size()) {
            res.push_back(s);
            return;
        }
        for (int i = st; i < s.size(); i++) {
            if (i > st && s[i] == s[st])
                continue;
            swap(s[st], s[i]);
            // In order to matain the sorted order, we could not swap back.
            // if we swapped up, then the if statement for deduplication would not work properly.
            // as we cannot swapback, we must pass be value instead of reference.
            dfs(s, st + 1);
        }
    }

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