组合数输出问题
题目描述
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1,2,…,n从中任取r个数。
现要求你输出所有组合。
例如n=5,r=3 所有组合为：
123,124,125,134,135,145,234,235,245,34512 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 5123,124,125,134,135,145,234,235,245,345
输入格式
一行两个自然数n,r(1<n<21,0≤r≤n)
输出格式
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
输出时，每个数字需要3个场宽。
输入输出样例
输入 #15 3输出 #1
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
简单来说，就是用回溯或者深搜进行枚举，从一个数出发，向每一种情况进行组合，标记已组合的情况，然后改变初始数值，再次进行组合，从而实现递归（注意递归边界）；
#include<bits/stdc++.h>
using namespace std;
int a[101];
int n,r,total = 0;
void dfs(int x,int y){
if(y>r){
for(int i = 1;i<=r;i++){
printf("%3d",a[i]);
}
printf("\n");
total++;
return;
}//深度优先搜索；
for(int i = x;i<=n;i++){
a[y] = i;
dfs(i+1,y+1);
}
}//x表示搜索到第几个值，y表示已经取了多少个数；
int main(){
cin>>n>>r;
dfs(1,1);
cout<<"total"<<" "<<total;
return 0;
}
还可以用回溯做
#include<bits/stdc++.h>
using namespace std;
int a[101],b[101];
int n,r,total = 0;
int print(){
total++;
for(int i = 1;i<=r;i++){
cout<<setw(3)<<a[i];
}
cout<<endl;
}
int search(int x){
for(int i = 1;i<=n;i++){
if(!b[i]){
a[x] = i;
b[i] = 1;
if(x == r) print();
else search(x+1);
b[i] = 0;
}
}
}
int main(){
cin>>n>>r;
search(1);
cout<<"total"<<" "<<total;
return 0;
}
题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
输入格式
输入：待拆分的自然数n。
输出格式
输出：若干数的加法式子。
输入输出样例
输入 #17输出 #1
1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4
这个问题与上一个问题的不同之处在于这次可以出现组合中的重复值，并且要将每一种情况都枚举出来，还要保证每一组之间各不重复；使用深搜可以高效地解决这一问题；
#include<bits/stdc++.h>
using namespace std;
int n,a[101];
void dfs(int x,int y,int z)//x表示当前取的数；y表示剩余值； z表示取个数；
{
if(y<0) return;
if(y == 0){
cout<<n<<" = ";
for(int i = 1;i<z;i++){
if(i!=1){
cout<<"+";}
cout<<a[i];
}
cout<<endl;
return;
}
for(int i = x;i<n;i++){
a[z] = i;
dfs(i,y-i,z+1);
}
}
int main(){
cin>>n;
dfs(1,n,1);
return 0;
}
总而言之，深度优先搜索与回溯是相通的，在很多情况下，他们的效果相近，但深搜在某些特定情况下效率更高，而且可以解决很多回溯难以解决的问题；同理于深搜和广搜；