可以添加組合數字以給出一定的總和

Question

有一個整數數組（例如3,4,5），如何找到所有可以添加到給定總和的組合？ （如：17）

對於例如將有四種方式的三個數字可以添加多達17：

• 5 + 5 + 4 + 3
• 5 + 4 + 4 + 4
• 5 + 3 + 3 + 3 + 3
• 4 + 4 + 3 + 3 + 3

你會如何編程計算這個？例如。使用javascript。

Answer 1

一般主題稱爲「整數分區」。搜索可能會出現一個您可以使用的算法。

Answer 2

這裏是一個可能的解決方案（我做盡管其效率不要求）：

1. 您創建包含數字的總和的數據結構。 （這個總和的價值以及構成它的所有數字）。
2. 你有一個數組A和一個目標總和TARGET。
3. 您排序陣列A.
4. 創建一個新的數組B，從A與上述的數據結構，其中在B中的每個元素是相應數量的在A.
5. 雖然總和初始化（B已經值）
   1. 你在A中的B添加的每一個號碼到數據結構（B現在將有B.length*A.length元件）
   2. 在B每次總和即TARGET是溶液
   3. 每個總和在B中至少TARGET從B中刪除

注意：如果A中元素的任意組合等於0，那麼程序永遠不會結束（如預期的那樣）。這意味着A必須具有大於0的所有元素。