[ 登录注册 ]

语言

NYOJ 1058 部分和问题 【DFS】

2017-07-14 10:40:23 admin 返回上一页

标签:nyoj 1058

部分和问题

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述
给定整数a1、a2、.......an,判断是否可以从中选出若干数,使它们的和恰好为K。
输入
首先,n和k,n表示数的个数,k表示数的和。
接着一行n个数。
(1<=n<=20保证不超int范围)
输出
如果和恰好可以为k,输出“YES”,并按输入顺序依次输出是由哪几个数的和组成,否则“NO”
样例输入
4 131 2 4 7
样例输出
YES2 4 7

简单的深搜

#include <stdio.h>int n k ok arr[22] vis[22] count;void DFS(int pos){if(count >= k){if(count == k){if(!ok){ok = 1; printf("YES
");}for(int i = 0; i < n; ++i)if(vis[i]) printf("%d " arr[i]);printf("
");}return;}for(int i = pos; i < n; ++i){count += arr[i];vis[i] = 1;DFS(i + 1);count -= arr[i];vis[i] = 0;}}int main(){while(scanf("%d%d" &n &k) == 2){ok = 0;for(int i = 0; i < n; ++i){scanf("%d" arr + i);vis[i] = 0;}count = 0; DFS(0);if(!ok) printf("NO
");}return 0;}


NYOJ 1058 部分和问题 【DFS】布布扣bubuko.com

NYOJ 1058 部分和问题 【DFS】

标签:nyoj 1058


文章来源:http://www.bozhiyue.com/yuyan/2017/0714/1484299.html
返回上一页    返回分类 上一篇:   下一篇:
相关