各位大大好 我上一個發問的問題-「數字組合可能性」，其實是為了解決現在這個問題 目前已經寫的出來數列的冪集合了，感謝回答的大大們 但是現在現實上的情況可能不適用於冪集合，因此再來請教 是這樣的 現在要寫一個程式，有一個數字及一數列，要求這一數字是由數列中的哪些數字加總的 非單一答案，所以要求顯示各種組合性 舉個例子： 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 而我的情況是，同一個組合裡，同一個數字只能出現一次 所以和「找零錢問題」不太一樣 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.33.32.180