> 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;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/lcof/mian-shi-ti-38.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.