Problem1406--简单背包问题(2.8)

1406: 简单背包问题(2.8)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

假设有一个背包,可以放入的最大重量为s。现有n件物品,重量分别为W1、W2、......Wn,均为正整数,从n件物品中挑选若干件,使得放入背包的重量之和正好为s。请你找出所有可能的放法,如果都不能,就输出0。1<=s<=2^31-1,1<=n<=100,1<=Wi<=100。

Input

第1行是n和s,第2行为n件物品的重量。

Output

从前往后找,输出符合条件的全部放法,以物品的编号输出,每行一种放法。如果都不能放,输出0。

Sample Input Copy

5 10
4 3 1 2 5 

Sample Output Copy

1 2 3 4
1 3 5
2 4 5

HINT

【样例解释】
第1行:4+3+1+2=10,编号是:1、2、3、4。
第2行:4+1+5=10,编号是1、3、5。
第3行:3+2+5=10,编号是2、4、5。

Source/Category