dfs 的全排列

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <string>
 5 #include <string>
 6 #include <cstring>
 7 #include <map>
 8 #include <utility>
 9 using namespace std;
10 const int  N = 1e2+20 ;
11 bool vis[N];
12 int a[N],n;
13 void dfs(int num,int n){
14     if(num==n){
15         for(int  i =0;i<n;i++){
16             printf("%d%c",a[i],i==n-1?'
':' ');
17         }
18         return ;
19     }
20     for(int  i=1;i<=n;i++){
21         if(!vis[i]){
22             vis[i]=1;
23             a[num]=i;
24             dfs(num+1,n);
25             vis[i]=0;        
26         }
27     }
28 }
29 int  main()
30 {
31     while(~scanf("%d",&n)){
32         memset(vis,0,sizeof(vis));
33         dfs(0,n);
34     }
35     return  0;
36  }

 1 //用于生成全排列的函数
 2 int a[N],n;
 3 void init()
 4 {
 5     for(int   i=0;i<4;i++){
 6         a[i]=i+1;
 7     }
 8 }
 9 int main()
10 {
11     init();
12     int cnt=0;
13     do{
14         for(int   i=0;i<4;i++)
15         printf("%d%c",a[i],i==3?'
':' '); 
16         cnt++;
17     }while(next_permutation(a,a+4));
18     printf("%d
",cnt);
19     return 0;
20 }

 1 //从1到n取出m个数
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <string>
 6 #include <string>
 7 #include <cstring>
 8 #include <map>
 9 #include <utility>
10 using namespace std;
11 const int  N = 1e2+20 ;
12 bool vis[N];
13 int n,m,a[N];
14 void dfs(int  num,int n){
15     if(num==m+1){
16         for(int  i =1;i<=m;i++)
17         {
18             printf("%d%c",a[i],i==m?'
':' ');
19         }
20         return ;
21     }
22     for(int i =a[num-1]+1;i<=n;i++){
23         if(!vis[i]){
24             vis[i]=1;
25             a[num]=i;
26             dfs(num+1,n);
27             vis[i]=0;
28         }
29     }
30 }
31 int  main()
32 {
33     while(~scanf("%d%d",&n,&m)){
34         memset(vis,0,sizeof(vis));
35         dfs(1,n);        
36     }
37     return  0;
38 }

 1 //有重复字符的全排列
 2 
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <iostream>
 7 #include <algorithm>
 8 using namespace std;
 9 const int N=1e3+9;
10 char s[N],buf[N];
11 int l;
12 bool vis[N];
13 void dfs(int num){
14     if(num==l){
15         printf("%s
",buf);
16         return  ;
17     }
18     for(int i =0;i<l;i++){
19         if(!vis[i]){
20             int j;
21             for(j=i+1;j<l;j++){
22                 if(vis[j]&&s[i]==s[j]){//重复：先用了s靠后的字符又满足字符一样 
23                     break;
24                 }
25             }
26             if(j==l){
27                 vis[i]=1;
28                 buf[num]=s[i];
29                 dfs(num+1);
30                 vis[i]=0;
31             }
32         }
33     }
34     
35 }
36 int  main()
37 {
38     while(~scanf("%s",s)){
39         memset(vis,0,sizeof(vis));
40         l =strlen(s);
41         buf[l]='';
42         dfs(0);
43     }
44     return 0;
45 }
46 
47 
48 
49 112
50 112
51 121
52 211

 1 //hdu   1016
 2 
 3 
 4 
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <cstring>
 8 #include <iostream>
 9 #include <algorithm>
10 using namespace std;
11 const int N=1e2+9;
12 int n;
13 bool vis[N];
14 int a[N];
15 bool prime(int n){
16     if(n==1) return false;
17     for(int i =2;i*i<=n;i++){
18         if(n%i==0) return  false;
19     }
20     return true;
21 }
22 void  dfs(int num,int n){
23     if(num==n&&prime(1+a[n-1])){
24         for(int i =0;i<n;i++){
25             printf("%d%c",a[i],i==n-1?'
':' ');
26         }
27         return ;
28     }
29     for(int   i=2;i<=n;i++){//1一定是第一个 
30         if(!vis[i]&&prime(i+a[num-1])){
31             vis[i]=1;
32             a[num]=i;
33             dfs(num+1,n);
34             vis[i]=0;
35         }
36     }
37 }
38 int f=1; 
39 int main()
40 {
41     while(~scanf("%d",&n)){
42         memset(vis,0,sizeof(vis));
43         a[0]=1;
44         printf("Case %d:
",f++);
45         dfs(1,n);
46         printf("
");
47     }
48     return 0;
49 }

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<vector>
 7 #include <cstdlib>
 8 #include <map>
 9 using namespace std;
10 #define mem(a,b) memset(a,b,sizeof(a))
11 const int N = 2e5+5;
12 pair<int,int>P;
13 vector<int> ve[N];
14 vector<pair<int,int> > que[N];
15 int  a[N],b[N];
16 int m;
17 int n,sum;
18 bool vis[N];
19 int cnt  = 0;
20 map<int,int>mp;
21 //从数组b里面取出若干个数，令其和为110 
22 void dfs(int num,int n){
23     {
24         if(num<=n&&sum==110) 
25         {
26             
27             
28 
29         
30     
31         
32             
33         
34             for(int j=1;j<=num-1;j++){
35                 printf("%d ",a[j]);
36             }
37             printf(":: %d 
",sum);
38         
39             return ;
40         }
41         for(int i =mp[a[num-1]]+1;i<=n;i++){
42             if(!vis[i]){
43                 vis[i] = 1;
44                 a[num]= b[i];
45                 sum+=b[i];    
46                 dfs(num+1,n);
47                 vis[i] = 0;
48                 sum-=b[i];
49             }
50         }
51     }
52 }
53 int main()
54 { 
55  sum =0;
56  mp[0]=0;
57 // scanf("%d%d",&n,&m);
58 scanf("%d",&n);
59 for(int i =1;i<=n;i++){
60     scanf("%d",&b[i]);
61     mp[b[i]] =i;
62 }
63     dfs(1,n);
64     return 0;
65 }