题目：
输入一个字符串，打印出该字符串中字符的所有排列。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：
把一个字符串看成两部分组成：第一部分为第一个字符，第二部分为后面的所有字符。
求整个字符串的排列，可以看出两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面的所有字符交换；然后固定第一个字符，求后面所有字符的排序。此时仍把后面的字符看成两部分，第一个字符和后面的字符，然后重复上述步骤。（递归）
在后面的在线测试中，要求输入字符串可能有重复的字符，输出按照字典顺序。
类似题目：
1、输入一个含有8个数字的数组，判断有么有可能把这8个数字分别放到正方体的8个顶点上，使得正方体上三组相对的面上的4个顶点的和相等。
思路：相当于求出8个数字的全排列，判断有没有一个排列符合题目给定的条件，即三组对面上顶点的和相等。
2、N皇后问题：在8 X 8的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处于同一行，同一列或者同意对角线上，求出所有符合条件的摆法。
思路：由于8个皇后不能处在同一行，那么肯定每个皇后占据一行，这样可以定义一个数组A[8]，数组中第i个数字，即A[i]表示位于第i行的皇后的列号。先把数组A[8]分别用0-7初始化，接下来对该数组做全排列，由于我们用0-7这7个不同的数字初始化数组，因此任意两个皇后肯定也不同列，那么我们只需要判断每个排列对应的8个皇后中是否有任意两个在同一对角线上即可，即对于数组的两个下标i和j，如果i-j==A[i]-A[j]或i-j==A[j]-A[i]，则认为有两个元素位于了同一个对角线上，则该排列不符合条件。
代码：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
void swap(char* c1,char* c2){
char tmp=*c1;
*c1=*c2;
*c2=tmp;
}
void permutation(char* pstr,char* pbegin){
if(*pbegin==' ')
printf("%s
",pstr);
else{
for(char* pCh=pbegin;*pCh!=' ';pCh++){
swap(pbegin,pCh);
permutation(pstr,pbegin+1);
swap(pbegin,pCh);
}
}
}
void permutationStr(char* pstr){
if(pstr==NULL)
return;
permutation(pstr,pstr);
}
int main()
{
char str[4]="abc";
permutationStr(str);
return 0;
}
在线测试OJ：
http://www.nowcoder.com/books/coding-interviews/fe6b651b66ae47d7acce78ffdd9a96c7?rp=2
AC代码：
class Solution {
public:
void swap(char* c1,char* c2){
char tmp=*c1;
*c1=*c2;
*c2=tmp;
}
void Permutation(string &str,int begin,vector<string> &result){
int len=str.length();
if(begin==len-1)
result.push_back(str);
else{
for(int i=begin;i<len;i++){
if(i==begin || str[i]!=str[begin]){
swap(&str[begin],&str[i]);
Permutation(str,begin+1,result);
swap(&str[begin],&str[i]);
}
}
}
}
vector<string> Permutation(string str) {
vector<string> result;
if(str.length()>0){
Permutation(str,0,result);
sort(result.begin(),result.end());
}
return result;
}
};