NYOJ之题目1058部分和问题

----------------------------------------

简单搜索+剪枝

因为考虑到可能会有多个解,所以是将中间过程保存最后才一起打印出来的

AC代码:

  1:
  2: import java.util.ArrayList;
  3: import java.util.List;
  4: import java.util.Scanner;
  5:
  6: public class Main {
  7:
  8: 	public static void main(String[] args) {
  9:
 10: 		Scanner sc=new Scanner(System.in);
 11:
 12: 		while(sc.hasNextInt()){
 13:
 14: 			int n=sc.nextInt();
 15: 			int k=sc.nextInt();
 16:
 17: 			int x[]=new int[n];
 18: 			for(int i=0;i<x.length;i++) x[i]=sc.nextInt();
 19:
 20: 			ans=new StringBuilder();
 21: 			dfs(x,0,k,new ArrayList<Integer>());
 22:
 23: 			System.out.println(ans.length()==0?"NO":ans);
 24: 		}
 25:
 26: 	}
 27:
 28: 	private static StringBuilder ans;
 29:
 30: 	public static void dfs(int x[],int i,int k,List<Integer> trackStack){
 31: 		if(k==0){
 32: 			if(ans.length()==0) ans.append("YES\n");
 33: 			for(int j=0;j<trackStack.size();j++) ans.append(trackStack.get(j)).append(" ");
 34: 			ans.append("\n");
 35: 			return;
 36: 		} else if(i==x.length || k<0) return;
 37:
 38: 		trackStack.add(x[i]);
 39: 		dfs(x,i+1,k-x[i],trackStack);
 40: 		trackStack.remove(trackStack.size()-1);
 41:
 42: 		dfs(x,i+1,k,trackStack);
 43: 	}
 44:
 45: }

题目来源: http://acm.nyist.net/JudgeOnline/problem.php?pid=1058

时间: 11-01

NYOJ之题目1058部分和问题的相关文章

NYOJ 1058 部分和问题 【DFS】

部分和问题 时间限制: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 简

NYOJ 搜索题目汇总 NYOJ 20、21、27、42、58、82、202、284、325、353、488、491、523、592、722

NYOJ 搜索题目汇总 NYOJ 20 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<algorithm> using namespace std; int pre[100005]; vector<int>v[100005];//存储每个结点相邻的边 void DFS(int

NYOJ 1058 部分和问题(经典题目dfs)

部分和问题 描述 给定整数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 题目分析: 这是一道经典的dfs问题,好多公司也用它做过面试题,我们定义函数dfs

nyoj 1058部分和问题

部分和问题 时间限制: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 #in

nyoj 1058部分和问题(DFS)

部分和问题 时间限制: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<cstdio>

nyist oj 1058 部分和问题 (DFS搜索)

部分和问题 时间限制: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 来

NYOJ:题目490 翻译

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=490 这题的输入输出格式好像描述的不太清楚,1)可能是所有数据都完成输入,然后再输出(解法1,内存可能不够,对题意通用性高(AC通过))2)也可能是待测试的数据输完一行就立马输出一行结果(解法2,内存能够,因为题意有歧义可能不能这样解(没通过))两种写法都写了,最后以第一种输入输出格式通过的,还好后台数据没有内存超出的 下面贴上代码: 解法1(AC): 1 //解法1,内存可能不够,对题

NYOJ:题目524 A-B Problem

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=860 My思路: 先用两个字符串储存这两个实数,然后再用另外两个字符串储存去掉符号和前后多余的0后的新"实数",最后只需要比较两个化简后的新字符就ok了. My代码实现: 1 #include<iostream> 2 using namespace std; 3 string simplify(string s) { //去字符串s的正负号和首尾多余的0 4 str

NYOJ:题目529 flip

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=529 由于此题槽点太多,所以没忍住...吐槽Time: 看到这题通过率出奇的高然后愉快的进来想水掉...but... 一开始狂百度找讨论区也完全看不懂题意啊, 还好后来通过这些零碎的线索补脑了下面的题意, 能AC但不很确定484题目本意,希望对大家有帮助(话说这样会不会帮倒忙啊^_^). 题目意思:要通过x的二进制的任意位置上的数(0变为1,或1变为0)使十进制的x变为x+1, 一次只能