全排列的两种写法 2021-02-17

1. // C 写法
2. #include <iostream>
3. using namespace std;
4. int a[10],book[10],n;
5. void dfs(int step,int t){
6.  if(step==t+1){
7.    for(int i=1;i<=t;i++)
8.      cout<<a[i]<<" ";
9.    cout<<endl;
10.     return;
11.   }
12.   for(int i=1;i<=n;i++){
13.     if(book[i]==0&&i>a[step-1]){
14.       a[step]=i;
15.       book[i]=1;
16.       dfs(step+1,t);
17.       book[i]=0;
18.     }
19.   }
20.   return;
21. }
22. int main(int argc, char *argv[])
23. {
24.   n=5;
25.   dfs(1,3);
26.   return 0;
27. }

1. // C++ 写法
2. #include <iostream>
3. #include <vector>
4. #include <algorithm>
5. using namespace std;
6. vector<vector<int> > res;
7. void backtrack(vector<int> &nums,vector<int> &track)
8. {
9.  if(3==track.size())
10.   {
11.     res.push_back(track);
12.     return;
13.   }
14.   for(vector<int>::iterator it=nums.begin();it!=nums.end();it++)
15.   {
16.     if(std::count(track.begin(),track.end(),*it) || (track.size()>0 && *it<track.back()))
17.       continue;
18.     track.push_back(*it);
19.     backtrack(nums,track);
20.     track.pop_back();
21.   }
22. }
23. void dfs(vector<int> nums)
24. {
25.   vector<int> track;
26.   res.clear();
27.   backtrack(nums,track);
28. }
29. int main(int argc, char *argv[])
30. {
31.   int a[]={1,2,3,4,5};
32.   vector<int> nums(a,a+sizeof(a)/sizeof(a[0]));
33.   dfs(nums);
34.   for(int i=0;i<res.size();i++)
35.   {
36.     for(vector<int>::iterator it=res[i].begin();it!=res[i].end();it++)
37.       cout<<*it<<" ";
38.     cout<<endl;
39.   }
40.   cout<<res.size()<<endl;
41.   return 0;
42. }