题目链接

题目描述
输入两个整数 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;
}
Last modification:September 21st, 2019 at 12:18 am
如果觉得我的文章对你有用,请随意赞赏