c130. 00574 - Sum It Up
Tags : 子集和問題
Accepted rate : 174人/200人 ( 87% ) [非即時]
評分方式:
Strictly

最近更新 : 2015-08-28 15:03

Content

給你一個總數 t ,和 n 個正整數的集合。請你找出用這 n 個數相加可以得到 t 的所有方式。例如:t=4,n=6,且這集合的內容為[4,3,2,2,1,1],那麼你將有4種不同的相加方式可以得到 t :4, 3+1, 2+2, 2+1+1 。(在一個加法中一個數字可以被使用的次數不可超過該數字出現在集合中的次數)

你的任務就是要解決這個問題。

Input

每筆測試資料一列。每列包含了 t , n 及 x1,x2,......xn。分別代表總數,集合中有多少個元素,及集合中的各數。其中 0 < t < 1000,1 <= n <= 12,0 < x1,x2,......xn < 100。

集合中的元素已由大到小排列。若n=0代表輸入結束。

Output

對每組測試資料,請先輸出一列"Sum of t :",接下來每種排列方式一列。數字需由大到小排列。不同的相加方式亦由大到小排列,即先比第1個數,若相同再比第2個數,依此類推。若找不到任何一種相加方式,請輸出"NONE"。

請參考Sample Output

Sample Input #1
4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0
Sample Output #1
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :

* Luck 貓翻譯

Tags:
子集和問題
出處:
UVa574

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」