问题 5037 --子集和问题2

5037: 子集和问题2★★★

时间限制: 3 Sec  内存限制: 512 MB
提交: 11  解决: 5
[提交][状态][命题人:]

题目描述

子集和问题的一个实例为〈S, c〉。其中,S={ x1 x2 xn}是一个正整数的集合,c是一个正整数。子集和问题判定是否存在S的一个子集S1,使得子集S1中所有元素的和等于c

对于给定的正整数的集合S={ x1 x2 xn}和正整数c,编程计算S 的一个子集S1,使得子集S1和等于c。如果有多组满足题意的答案,我们约定只选择字典序最小的那一种情况:例如,1+3+5=2+3+4=9,135<234,故答案为1 3 5。再比如12+5+42=5+40+14=59,因为12542<54014,故答案为12 5 42

输入

文件第1行有2个正整数n<200cn表示S的个数,c是子集和的目标值。

接下来的1 行中,有n个正整数,表示集合S中的元素。

输出

输出子集和问题的最小字典序解

当问题无解时,输出-1

样例输入
Copy
8 27
9 12 31 7 5 6 4 17
样例输出
Copy
12 5 6 4

提示

满足要求解有[9,12,6],[9,7,5,6],[12,5,6,4],[6,4,17],其中第三种的字典序12564最小。

把每种方案的数连在一起构成字符串,再按字典序比较大小

来源

[提交][状态]