题解 | 全排列

#include <iostream>
#include <string>
using namespace std;

void solve(string pre, string str) {
    if (str.length() == 1) {
        cout << pre + str << endl;
        return;  // 加上return使逻辑更清晰
    }
    string new_pre, new_str;
    for (int i = 0; i < str.size(); i++) {
        new_pre = pre + str[i];
        // 先复制再删除，不修改原始str
        new_str = str;
        new_str.erase(i, 1);
        solve(new_pre, new_str);
    }
}

int main() {
    string str;
    while (cin >> str) { 
        solve("", str);
    }
    return 0;
}

这里搬运一个大佬的思路：

【递归思路】：递归有两个必要条件：

1. 子问题与原问题必须相同且规模更小；
2. 不能无限制地调用本身，必须有一个递归出口。

【此问题思路】：

abc的全排列 = a开头bc的全排列 + b开头ac的全排列 + c开头ab的全排列

其中在啊开头的情况在，bc的全排列 = ab开头c的全排列 + ac开头b的全排列

以此类推......

关键点：

str.erase(i,1)会直接修改原字符串（调用它的字符串对象），并返回修改后的字符串；

在代码中要注意先赋值后再修改，防止erase修改了原字符串；