Nguồn:
http:/codeforces.com
Pari
wants to buy an expensive chocolate from Arya. She has n coins, the value of the i-th coin is ci. The price of the chocolate
is k, so Pari will take a subset
of her coins with sum equal to k and give it to Arya.
Looking
at her coins, a question came to her mind: after giving the coins to Arya, what
values does Arya can make with them? She is jealous and she doesn't want Arya
to make a lot of values. So she wants to know all the values x, such that Arya will be able
to make xusing some subset of coins
with the sum k.
Formally,
Pari wants to know the values x such that there exists a subset of coins
with the sum k such that some subset
of this subset has the sum x, i.e. there is exists some way to pay for the
chocolate, such that Arya will be able to make the sum x using these coins.
Input
The
first line contains two integers n and k (1 ≤ n, k ≤ 500) — the number of coins
and the price of the chocolate, respectively.
Next
line will contain n integers c1, c2, ..., cn (1 ≤ ci ≤ 500) — the values of Pari's
coins.
It's
guaranteed that one can make value k using these coins.
Output
First
line of the output must contain a single integer q— the number of suitable
values x. Then print q integers in ascending
order — the values that Arya can make for some subset of coins of Pari
that pays for the chocolate.
Examples
|
Input
|
Output
|
|
6
18
5 6 1 10 12 2 |
16
0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 |
|
|
|
|
3 50
25 25 50 |
3
0 25 50 |
Tóm tắt đề: cho một dãy gồm N số và 1 số nguyên K
đề bảo ta rằng : Trong toàn
bộ tập hợp có tổng = k
thì in ra tổng các tập hợp
con của tập hợp đó
