类似dfs全排列问题。

有一道相似的题目，可以参考acwing的解析：AcWing 842. 排列数字–深度优先遍历代码+注释 – AcWing，题目如下：

给定一个整数 nn，将数字 1∼n排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。

算法：

• 用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
• 用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。
• dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
• 回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。

#include <iostream>
using namespace std;
int n;
int path[10];
bool st[10];

void dfs(int u, int n) { //从第u个位置开始看, u代表当前的位数
    if (u == n) { // u已经到达n了，说明递归到头了
        for (int i = 0; i < n; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    }
    for (int i = 1; i <= n; i++) {
        if (st[i] == false) { // 如果数字 i 没有被用过
            path[u] = i;
            st[i] = true;
            dfs(u + 1, n);
            // 递归出来，恢复现场
            path[u] = 0;
            st[i] = false;
        }
    }
}
int main() {
    cin >> n;
    dfs(0, n); //从第u个位置开始看
    return 0;
}

本题和排数字差不多，题解如下（摘自牛客）：

#include <vector>
class Solution {
  public:

    std::unordered_set<string> set;
    vector<bool> state;
    string path;

    vector<string> Permutation(string str) {
        if(str.empty()) return {};
        state.resize(str.size() + 10, false);
        dfs(0, str);
        vector<string> ans;
        for(auto& s : set){
            ans.emplace_back(s);
        }
        return ans;
    }
    void dfs(int u, string& str) {
        if(u == str.size()){
            set.insert(path);
        }
        for(int i = 0; i<str.size(); ++i){
            if(state[i] == false){
                state[i] = true;
                path.push_back(str.at(i));
                dfs(u+1, str);
                // 回溯状态
                state[i] = false;
                path.pop_back();
            }
        }
    }
};