各位大大好
我上一個發問的問題-「數字組合可能性」，其實是為了解決現在這個問題
目前已經寫的出來數列的冪集合了，感謝回答的大大們
但是現在現實上的情況可能不適用於冪集合，因此再來請教
是這樣的
現在要寫一個程式，有一個數字及一數列，要求這一數字是由數列中的哪些數字加總的
非單一答案，所以要求顯示各種組合性
舉個例子： 90 是由 {30, 20, 50, 40, 60} 這些數字中的哪些數字加總起來的
可能組合性有..
組合一： 50 + 40 = 90
組合二： 30 + 60 = 90
組合三： 30 + 20 + 40 = 90
這個程式就是像這樣，要讓使用者輸入total和數列，程式再跑出所有組合情況
原本我的想法是用冪集合展開數列中所有數字的組合可能性，
讓各個組合做加總，加總後再去判斷哪個數字等於user輸入的total
等於total的那個組合就是答案了
想說這樣絕對不會miss，因為所有的組合性都會跑過、檢查過，正確性也有
但問題來了，這方式只適用數列個數很小的時候
當數列個數大於20的時候，程式就開始跑很久了
我算過當個數是30時，組合性有10億，每種組合要跑過的話，迴圈至少要跑10億圈
問過user，他們最多有可能到50個數字
所以想請教，有沒有什麼方式或演算法可以解決?
謝謝
另外，我問過數學系的朋友，他的回答也跟我的想法一樣
（就是冪集合的方式，一組一組檢查），可是這樣個數多時會很久
也想過「找零錢問題」
像是 http://tw.myblog.yahoo.com/dust512/article?mid=-2&prev=14&l=a&fid=5
可是「找零錢問題」的情況和我的問題不太一樣，「找零錢問題」的零錢面額可以有
很多個，例如：10元硬碟*n
而我的情況是，同一個組合裡，同一個數字只能出現一次
所以和「找零錢問題」不太一樣