题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路
方法一：递归
1、思路：假设字符串长度为n，则字符串全排列的数目一共有种，首先固定字符串的第一位，一共有n种选择，然后固定第二位，有n-1种选择，因此可以递归的固定字符串的每一位，当固定到字符串的最后一位时开始回溯，用set可以自动对字符串的排列进行排序，还可以去除重复排列。
2、代码：
class Solution {
public:void perm (int pos, string str, set<string> &tmp) {if (pos + 1 == str.length()) {tmp.insert(str);return;}for (int i = pos; i < str.length(); i++) {swap(str[pos], str[i]);perm(pos + 1, str, tmp);swap(str[i], str[pos]);}}vector<string> Permutation(string str) {vector<string> result;if(str.empty()) return result;set<string> tmp;perm(0, str, tmp);result.assign(tmp.begin(), tmp.end());return result;}
};3、复杂度：
时间复杂度：O(n!)；
空间复杂度：O(n!)，最多需要保存n!个排列。