面试题：全排列

求全排列：

递归版本，去除重复

 1 #include <iostream>
 2 #include <string>
 3 #include <memory.h>
 4 #include <vector>
 5 using namespace std;
 6 
 7 //全排列
 8 vector<vector<int> > res;
 9 void perm(vector<int> &arr,int s,int e,vector<int> &restmp)
10 {
11     if(s == e)
12     {
13         restmp.push_back(arr[s]);
14         res.push_back(restmp);
15         return;
16     }
17     else
18     {
19         int i;
20         for(i = s ； i <= e ; ++i)
21         {
22             int j;
23             bool flag = true;
24             for(j = s ; j < i ; ++j)
25             {
26                 if(arr[j] == arr[i])
27                 {
28                     flag = false;
29                 }
30             }
31             if(!flag)
32                 continue;
33             swap(arr[i],arr[s]);
34             restmp.push_back(arr[i]);
35             perm(arr,s+1,e,restmp);
36             restmp.pop_back();
37             swap(arr[i],arr[s]);
38         }
39     }
40 }
41 
42 int main()
43 {
44     return 0;
45 }

非递归版本：

主要是涉及next_permutation算法：就是找当前排列的下一个排列，主要思想是从后往前找第一个逆序的数，然后从后往前第一个比找到数大的字符位置交换，再讲后面的子串反转即可。

具体参考：

http://blog.csdn.net/morewindows/article/details/7370155/