时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路：
递归法，问题转换为先固定一个字符，求剩余字符的排列；求剩余字符的排列时跟原问题一样。
1》遍历所有可能出现在第一个位置的字符（即，依次将第一个字符同后面的所有字符交换）
2》固定第一个字符，求后面字符的排列（即，在第一个的遍历过程中，插入递归进行实现）
注意：
1》先确定递归结束的条件：本题中设begin==str.size()-1
2》形如aba或aa等特殊测试用例的情况，vector在进行push_back时是不考虑重复情况的，需要自行控制。
3》输出的排列可能不是字典顺序排列的，可能导致无法完全通过测试用例，考虑输出前排序，或者递归之后取消复位操作。
class Solution { public: vector<string> Permutation(string str) { vector<string> result; if(str.empty()) return result; Permutation(str,result,0); //此时得到的result中排序并不是字典顺序，需要单独排序 sort(result.begin(),result.end()); return result; } void Permutation(string str,vector<string>& result,int begin) { if(begin == str.size()-1) { if(find(result.begin(),result.end(),str)== result.end()) { //如果result中不存在str才添加，避免aa和aa重复添加 result.push_back(str); } } else { for(int i = begin;i < str.size();i++) { // 第一次循环i与begin相等，相当于第一个位置自身交换，关键在于之后的循环， // 之后i != begin，则会交换两个不同位置上的字符，直到begin==str.size()-1，进行输出； swap(str[i],str[begin]); Permutation(str,result,begin+1); // 复位，用以恢复之前字符串顺序，达到第一位依次跟其他位交换的目的 swap(str[i],str[begin]); } } } void swap(char &fir,char &sec) { char temp = fir; fir = sec; sec = temp; } };
原文：https://www.cnblogs.com/whiteBear/p/12571294.html