002 - チーム虚無新人賞おめでとう！

問題

ところで、n個の自然数があった。i番目はa_iである。

自然数xが与えられるので、自然数をn個から１個以上選んだ時にその総和がxになる組み合わせの数を出力せよ。

入力

n x
a1 
a2 
・
・
・
an

制約

すべての入出力ケースにおいて以下を満たす。

• 2≦n≦30 1≦x≦1000 1≦a_i≦30

小課題

小課題１[1点]

• n≦20

小課題2[9点]

• 追加の制約はない

入出力例

入力例1

2 2
1
1

1+1の一通りである。

出力例1

1

入力例2

3 3
1
2
3

1+2と3の二通りである。

出力例2

2

入力例3

10 41
1
2
3
4
5
6
7
8
9
10

出力例3

17

解説（クリックで開く）

この問題は、部分和問題という有名な問題です。解法はDPです。DPを用いればn≦100でも間に合うのですが、制約が小さいため、他の解法でも求めることができます。具体的な解法に関しては、調べた方が分かりやすいので割愛します。