首页 > 代码库 > NYOJ之题目1058部分和问题
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
NYOJ之题目1058部分和问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。