思路

递归回溯问题,例如 abc,我们可以在每一次递归的时候把某一个字母放到最前面,就是 swap 一下,就变成了分别从 abc、bac、cba 开始的字符串,然后后面的两个字母也可以选择任意一个放到“开头”,以此类推

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void backtrace(vector<string>& ans, string s, int start, int len){
    if(start == len){
        ans.push_back(s);
        return;
    }
    for(int i = start; i < len; i ++){
        swap(s[i], s[start]);
        backtrace(ans, s, start + 1, len);
        swap(s[i], s[start]);
    }
}
int main(){
    string s;
    while(cin >> s){
        vector<string> ans;
        backtrace(ans, s, 0, s.size());
        sort(ans.begin(), ans.end());
        for(string c : ans)
            cout << c << endl;
    }
    return 0;
}