1043 . F.名偵探蚵男
TopCoder
Description
米花市出了一個大案件：重達近千斤的貨櫃一靠港立即不翼而飛，警方急著尋找貨櫃主人，卻發現主人橫死在自己家裡反鎖的浴室！名偵探蚵男再一次得到任務，他必須找出貨櫃裡究竟藏有什麼，並解開密室殺人案。
所幸當初將東西搬上貨櫃的工人並未受到襲擊，根據他的說法，貨櫃裡有許多不同的貨品，包裝得很隱密，因此只知道貨櫃總重量以及每種貨品多重。至於每種貨品各有多少個，很遺憾地工人並不記得。警方想要分析這個貨櫃可能的組合方式，卻發現問題意外地複雜，舉例來說，貨櫃重10公斤，貨品有4種，分別為1、2、3、5公斤：
10=5+5=5+3+2=5+3+1+1=5+2+1+1+1=5+1+1+1+1+1=…=1+1+1+…+1
總計竟有高達20種可能性！
身為蚵男，你是否能利用程式找出所有可能的組合情形，幫助無力的警方呢？
Input Format
輸入檔包含了多筆的測試資料。每筆資料兩行，第一行為一個正整數N（1≦N≦100）表示貨品種類數以及一個正整數P（1≦P≦10000）表示貨櫃總重；第二行包含N個相異正整數表示N種貨品的重量，同一行內的數字將以一個空白鍵分隔。最後一筆資料結束後會有一行0 0表示結束。
Output Format
針對每筆資料輸出一個整數，即貨櫃可能的組合情形，並以換行分隔。注意答案不一定總是小於232。
Sample Input 1
3 10
11 12 13
4 10
1 2 3 5
0 0
11 12 13
4 10
1 2 3 5
0 0
Sample Output 1
0
20
20
Hints
※2007/10/07:測資出現問題，已修正。感謝各位因為long long炸掉的同胞們XD
(這年的問題這麼多，到底是怎樣= =+，還是自己出題好了|||)
(我看到232 就很高興的用unsigned int...)
Problem Source
原TIOJ1043 / NPSC2003初賽(prob F)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |