题目描述
排列与组合是常用的数学方法,其中组合就是从n个元素中抽出r个元素(不分顺序且r < = n),我们可以简单地将n个元素理解为自然数1,2,…,n,从中任取r个数。
现要求你不用递归的方法输出所有组合。
例如n = 5 ,r = 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
输入
一行两个自然数n、r ( 1 < n < 21,1 < = r < = n )。
输出
所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,所有的组合也按字典顺序。
- 本题与上题全排列略有不同
#include<bits/stdc++.h> using namespace std; int n,r,print[10]={0}; int visit[10]={false}; void dfs(int now,int sum_num){ if(sum_num==r){ for(int i=0;i<r;i++){ printf("%d ",print[i]); } printf("\n"); return;//递归边界 }else{ for(int i=print[sum_num-1]+1;i<=n;i++){//与全排列不同 if(visit[i]==false){ print[sum_num]=i; visit[i]=true; sum_num++; dfs(i,sum_num);//选取当前的数 //回溯 visit[i]=false; sum_num--; } } } } int main(){ while(scanf("%d %d",&n,&r)!=EOF){ fill(visit,visit+n,false); fill(print,print+n,0); dfs(0,0); } return 0; }
解法2:index非常适合有顺序选择的情况
-
#include<bits/stdc++.h> using namespace std; int n,r; vector<int>a; void dfs(int index,int cnt){ if(cnt==r){//边界条件 for(int i=0;i<r;i++){ printf("%d ",a[i]); } printf("\n"); return; } if(index==n) return; a.push_back(index+1); dfs(index+1,cnt+1); a.pop_back(); dfs(index+1,cnt); } int main(){ while(scanf("%d %d",&n,&r)!=EOF){ dfs(0,0); } return 0; }
原文链接: https://www.cnblogs.com/YanShaoDian/p/12676550.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/341226
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!