【問題E10】名偵探蚵男。 [回前頁]
米花市出了一個大案件:重達近千斤的貨櫃一靠港立即不翼而飛,警方急著尋找貨櫃主人,卻發現主人橫死在自己家裡反鎖的浴室!名偵探蚵男再一次得到任務,他必須找出貨櫃裡究竟藏有什麼,並解開密室殺人案。
所幸當初將東西搬上貨櫃的工人並未受到襲擊,根據他的說法,貨櫃裡有許多不同的貨品,包裝得很隱密,因此只知道貨櫃總重量以及每種貨品多重。至於每種貨品各有多少個,很遺憾地工人並不記得。警方想要分析這個貨櫃可能的組合方式,卻發現問題意外地複雜,舉例來說,貨櫃重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種可能性!
身為蚵男,你是否能利用程式找出所有可能的組合情形,幫助無力的警方呢?
輸入檔說明
輸入檔包含了多筆的測試資料。每筆資料兩行,第一行為一個正整數N(1≦N≦100)表示貨品種類數以及一個正整數P(1≦P≦10000)表示貨櫃總重;第二行包含N個相異正整數表示N種貨品的重量,同一行內的數字將以一個空白鍵分隔。最後一筆資料結束後會有一行0 0表示結束。
輸出檔說明
針對每筆資料輸出一個整數,即貨櫃可能的組合情形,並以換行分隔。注意答案總是小於232。
範例輸入
3 10
11 12 13
4 10
1 2 3 5
0 0
範例輸出
0
20