全排列和组合

全排列递归写法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int a[100];
 5 bool vis[100];
 6 void dfs(int x)
 7 {
 8     if(x>n){
 9         for(int i=1; i<=n; i++)cout<<a[i]<<" ";
10         cout<<endl;
11         return;
12     }
13     for(int i=1; i<=n; i++)
14     {
15         if(!vis[i])
16         {
17             a[x]=i;
18             vis[i]=1;
19             dfs(x+1);
20             vis[i]=0;
21         }
22     }
23 
24 }
25 int main()
26 {
27     cin>>n;
28     dfs(1);
29     return 0;
30  }

对应练习题：https://www.luogu.com.cn/problem/P1706

组合数递归写法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, k, ans=0;
 4 int a[25];
 5 bool vis[25];
 6 
 7 void dfs(int step)
 8 {
 9     if(step>k){
10         for(int i=1; i<=k; i++)cout<<a[i]<<" ";
11         cout<<endl;
12         return;
13     }
14     for(int i=a[step-1]+1; i<=n; i++)//注意跟上面全排列最大的区别地方
15     {
16         if(!vis[i])
17         {
18             a[step]=i;
19             vis[i]=1;
20             dfs(step+1);
21             vis[i]=0;
22         }
23     }
24 
25 }
26 int main()
27 {
28     
29     cin>>n>>k;
30     dfs(1);
31     return 0;
32 }

对应练习题：https://www.luogu.com.cn/problem/P1036