问题 O: 【回溯法】组合的输出
题目描述
排列与组合是常用的数学方法,其中组合就是从n个元素中抽出r个元素(不分顺序且r<=n),我们可以简单地将n个元素理解为自然数1,2,…,n,从中任取r个数。
现要求你不用递归的方法输出所有组合。
例如n=5,r=3,所有组合为:
l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
输入
一行两个自然数n、r(1<n<21,1<=r<=n)。
输出
所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占三个字符的位置,所有的组合也按字典顺序。
样例输入
5 3
样例输出
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
这个题是典型的回溯,让我对回溯的清空状态有了一定的理解,写成了dfs。代码如下:
1 #include <bits/stdc++.h>
2 int n,r,a[25];
3 bool vis[25];// 来记录各个数字是否被访问
4 using namespace std;
5 void dfs (int dep)//dep代表搜索的深度,即当前数组a添加了多少个数
6 {
7 for (int i=a[dep-1]+1;i<=n;++i)//从上一个添加的数+1开始搜索数字
8 {
9 if (!vis[i])//如果这个数字没被访问过
10 {
11 a[dep]=i;//将这个数字添加到a里面去
12 if (dep==r)//如果添加的数字达到r个,把他们输出
13 {
14 for (int j=1;j<=r;++j)
15 printf("%3d",a[j]);
16 printf("\n");
17 }
18 else
19 dfs(dep+1);//如果达不到r个继续添加
20 vis[i]=0;//回溯,清空当前状态,把vis[i]设为没有访问过。
21 }
22 }
23 }
24 int main()
25 {
26 while (~scanf("%d%d",&n,&r))
27 {
28 memset(a,0,sizeof a);
29 memset(vis,false,sizeof vis);
30 dfs(1);//写成dfs很巧妙
31 }
32 return 0;
33 }
34 /*
35 Time:12 ms
36 Memory:1696 kb
37 */
原文链接: https://www.cnblogs.com/agenthtb/p/5759556.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/238513
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!