思路
递归回溯问题,例如 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; }