Challenge-2.1.4 部分和问题

部分和问题

描述

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

输入

首先，输入n，表示数的个数。
接着一行n个数。

（1<=n<=20,保证不超int范围）

下一行输入k，表示数的和

输出

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

样例输入

4 
1 2 4 7

13

样例输出

YES

简单的dfs

#include
using namespace std;
#define MAX_N 30
int a[MAX_N];
int n,k;


bool dfs(int i,int sum)//已经从前i项得到了和sum，然后对于 i 项之后的进行分支
{
if(i==n)return sum==k;//如果前n项都计算过了，则返回sum是否与k相等
if(dfs(i+1,sum))return true;//不加a[i]
if(dfs(i+1,sum+a[i]))return true;//加a[i]
return false;//是否加上a[i]都不能凑成k
}


int main()
{
cin>>n;
for(int i=0;i {
cin>>a[i];
}
cin>>k;
if(dfs(0,0))
cout<<"YES"< else
cout<<"NO"< return 0;
}

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力??

上一篇： poj 2151 Check the difficulty of problems(概率DP)

下一篇： A new Graph Game

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");