- 题目描述：
-
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
- 输入：
-
每个测试案例包括1行。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
- 输出：
-
对应每组数据,按字典序输出所有排列。
样例输入：
abc BCA样例输出：
abc acb bac bca cab cba ABC ACB BAC BCA CAB CBA【解题思路】由于需要字典序，首先肯定是要先对所给的字符串进行排序，然后很容易想到穷举法，但这边穷举法还有要避免重复，所以，有一定的技巧。我们有三个元素abb，最后输出时三元组，则我们可以将三个位置都看做由所有元素来填充的序列。负责度应该是一个n的n次方，但中间可以有一些剪枝。
由于n的大小不固定，我们没法确定是几层循环，所以只能用递归操作来进行遍历。对每一次递归调用都遍历n个元素哪个适合加入到结果队列res中，同时，我们设置一个used变量来控制某个元素是否已经在res中，避免重复添加。当检测到res的长度已经等于n，也即res中包含了所有的元素，则res中存在了一个合法的输出，我们输出结果。
当然，对于abb这种情况，我们需要对bb做特殊处理即我们不会输出1 2 3这种情况，至会输出1 3 2这种排列。具体就是当检测到某元素与之前的元素相等时我们跳过该元素。对于abb这种情况，遍历的顺序见下图。
AC code：
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
void permutation(vector<char> &res,string &str,vector<int> &used)
{
if(res.size()==str.length())
{
for(int i=0;i<res.size();++i)
printf("%c",res[i]);
printf("
");
return;
}
for(int i=0;i<str.length();++i)
{
if(used[i] || (i!=0 && str[i]==str[i-1] && used[i-1]))
continue;
used[i]=1;
res.push_back(str[i]);
permutation(res,str,used);
used[i]=0;
res.pop_back();
}
}
int main()
{
string strin;
while(cin>>strin)
{
vector<int> used(10,0);
sort(strin.begin(),strin.end());
vector<char> res;
permutation(res,strin,used);
}
return 0;
}
/**************************************************************
Problem: 1369
User: huo_yao
Language: C++
Result: Accepted
Time:530 ms
Memory:1520 kb
****************************************************************/