NYOJ 1058 部分和问题 【DFS】
2024-08-26 18:50:22
部分和问题
时间限制: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
简单的深搜
#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\n");
}
for(int i = 0; i < n; ++i)
if(vis[i]) printf("%d ", arr[i]);
printf("\n");
}
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\n");
}
return 0;
}
最新文章
- oracle过滤字母
- C语言atan2()函数:求y/x的反正切值
- 使用ajax获取JSON数据的jQuery代码的格式
- [IIS]IIS扫盲(七)
- 多功能表单填报系统V1.2.1-适用于在线报名系统、调查、数据收集等
- easyui的基本用法
- [java学习笔记]java语言基础概述之运算符&;程序流程控制&;for循环嵌套
- Repo安装遇到问题
- 【转】深入理解Java内存模型(三)——顺序一致性
- python函数abs()
- Struts2基础学习(三)&mdash;Result和数据封装
- Java jvm级别native关键词、JNI详解
- RunLoop想入门,看这篇就够了
- oracle创建触发器及作用举例
- 1Nginx+fastdfs分布式文件存储
- subclipse下svn: E200015: authentication cancelled问题的解决
- Spring Boot——Linux 启动方式
- mssql sqlserver 视图如何加密,让第三方用户查看不到其中的SQL语句
- linq总结系列(一)---基础部分
- 树状数组解决LIS---O(nlogn)