题目描述
输入两个整数 n 和 m,从数列1,2,3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 20;
int num[maxn];
int vis[maxn];
int stc[maxn];
int n,m,ans;
int dfs(int sum,int s);
int main()
{
while(cin>>n>>m)
{
ans=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i) num[i]=i;
dfs(0,0);
// cout<<ans<<endl;
}
return 0;
}
int dfs(int sum,int s)
{
if(sum==m)
{
int flag=1;
for(int i=0;i<s-1;i++)
{
if(stc[i]>stc[i+1])
{
flag=0;
break;
}
}
if(flag)
{
cout<<stc[0];
for(int i=1;i<s;++i)
{
cout<<" "<<stc[i];
}
cout<<endl;
}
return 0;
}
for(int i=1;i<=n;++i)
{
if(vis[i]) continue; //如过被访问过,则寻找下一个数
sum+=num[i]; //更新sum值
stc[s]=num[i];
s++;
vis[i]=1; //i已经被访问过了
dfs(sum,s); //进行下一步搜索
s--;
vis[i]=0;
sum-=num[i];
}
return 0;
}