部分和问题

素颜马尾好姑娘i 2022-08-07 13:50 163阅读 0赞

## 部分和问题 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 2

描述

给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。

输入

首先，n和k，n表示数的个数，k表示数的和。  
接着一行n个数。  
（1<=n<=20,保证不超int范围）

输出

如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成，否则“NO”

样例输入

4 13
    1 2 4 7

样例输出

YES
    2 4 7

来源

[经典题目][Link 1]

上传者

[TC\_杨闯亮][TC]

这个是深度优先搜索，不过这个深度优先搜索不是图而是一个线

性的数组，感觉用多重循环就可以写！但是太麻烦！这个就是仿

照多重循环的思路来的！

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    bool success,visit[25];
    int n,k,sum,a[25];
    void dfs(int pos)
    {
        int i;
        if(success==true)
        {
            return ;
        }
        if(sum>=k)
        {
            if(sum==k)
            {
                success=true;
                cout<<"YES"<<endl;
                for(i=0;i<n;i++)
                {
                    if(visit[i])
                    {
                        cout<<a[i]<<" ";
                    }
                }
                cout<<endl;
            }
            return ;//上面是判断
        }
        for(i=pos;i<n;i++)
        {
            sum+=a[i];//第一个被标记也就是被搜索
            visit[i]=1;
            dfs(i+1);//然后向前搜索！
            sum-=a[i];
            visit[i]=0;
        }
    }
    int main()
    {
        int i;
        while(cin>>n>>k)
        {
            memset(visit,0,sizeof(visit));
            sum=0;
            for(i=0;i<n;i++)
            {
                cin>>a[i];
            }
            success=false;
            dfs(0);//从0开始搜索
            if(!success)
            {
                cout<<"NO"<<endl;
            }
        }
    }

上面的搜索顺序是这样的！  
1

1 2

1 2 4

1 2 4 7

1 2 7

1  4

1 4 7

2 4

2 4 7符合，停止！

![Center][]

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%BB%8F%E5%85%B8%E9%A2%98%E7%9B%AE
[TC]: http://acm.nyist.net/JudgeOnline/profile.php?userid=TC_%E6%9D%A8%E9%97%AF%E4%BA%AE
[Center]: /images/20220805/bd98389adede4fe5a8b93d36d5959e4c.png