b040: 以物易物

遠古時代，當貨幣制度還沒有產生之前，人們是用以物易物的方式來交換所需要的物資。大南中古交換中心就是以類似的模式在經營，不同的是他們會將裡面所有的物品標價，而當顧客拿東西要來交換的時候，他們會先幫顧客的物品先估一個價格，而顧客則可以從裡面現有的物品裡挑選一個以上，只要加起來的價格沒有超過顧客帶來物品的價格，交易就算成立。
今天小雅來到大南中古交換中心，因為小雅是個非常精打細算的人，如果所挑選的物品的總價比她所帶來的東西低，則她不會從事這次的交易。現在給你交換中心裡所有物品的價格，以及小雅帶來的東西的價格，請你找出她有幾個不同的交易方式，或者不會進行交易。

輸入說明：

輸入資料第一行有兩個正整數 N、M (1<=N<=20、1<=M<=100000000)，N 代表交換中心有幾種物品，M 代表小雅帶來的物品的價格。第二行有 N 個正整數 Ai，即交換中心 N 種物品的價格 (1<=Ai<=M)，而且這些價格都不會相同。

輸出說明：

請輸出所有小雅可以交易的方式，每種方式以一行輸出，將要交換的物品價格依照原本輸入的順序輸出。有多組交易方式時，請以前幾項物品取的方式優先。而如果找不到一種交易方式所交換的物品價格和小雅帶來的東西相等，則請輸出 NO。

範例輸入：

4 31
11 13 24 7

範例輸出 ：

11 13 7
24 7

def ssum(list, sum1):
  current = ""
  ssum_h(list, len(list), current, sum1)

def ssum_h(list, n, subset, sum1):
  if sum1 == 0:
    print (subset)
    return
    
  if n == 0:
    return
    
  if list[n-1] <= sum1:
    ssum_h(list, n-1, subset, sum1)
    ssum_h(list, n-1, subset+ str(list[n-1]) + " ", sum1-list[n-1])
  else:
    ssum_h(list, n-1, subset, sum1)

if __name__ == "__main__":
    lst = []
    print("請輸入 各種物品的價格 或按enter結束")
    while True:
        lst1 = (input())
        if lst1:
            lst.append(int(lst1))
        else:
            break
    text = '\n'.join(str(lst))

    print()
    print("輸入資料",lst)
    print("輸入物品的價格 -> ",end='')
    sum1 = int(input())

    ssum(lst, sum1)

請輸入 各種物品的價格 或按enter結束
2
1
3
4
5
5
1
2
8
7
-2


輸入資料 [2, 1, 3, 4, 5, 5, 1, 2, 8, 7, -2]
輸入物品的價格 -> 7
4 1 2 
4 3 
5 2 
5 2 
1 3 1 2 
1 4 2 
1 5 1 
1 5 1 
2 3 2 
2 4 1 
2 5 
2 5 
2 1 3 1 
2 1 4 
7 
-2 4 3 2 
-2 5 3 1 
-2 5 4 
-2 5 3 1 
-2 5 4 
-2 1 4 3 1 
-2 1 5 1 2 
-2 1 5 3 
-2 1 5 1 2 
-2 1 5 3 
-2 2 4 1 2 
-2 2 4 3 
-2 2 5 2 
-2 2 5 2 
-2 2 1 3 1 2 
-2 2 1 4 2 
-2 2 1 5 1 
-2 2 1 5 1 
-2 8 1 
-2 8 1 
-2 7 2 
-2 7 1 1 
-2 7 2 
>>>