Teilmengen-Summenalgorithmus mit Wiederholung von Zahlen in der Menge
Ich habe eine Menge S, die natürliche Zahlen enthält, und ein Ziel t, bei dem es sich um eine Zahl handelt. Ich möchte gerne wissen
Wie können wir die Anzahl der möglichen Kombinationen dieser Zahlen finden, die sich zu Ziel t summieren?
Eine Zahl kann beliebig oft genommen werden und es können beliebig viele Zahlen genommen werden, um das zu erhalten
Summe gleich dem Ziel t.
Example
target 6
Set s {3,8,1,2}
Solution 3+3, 3+2+1, 1+1+1+3, 2+2+2, 2+1+1+2, 2+1+1+1+1, 1+1+1+1+1+1
Total No of solutions possible 7
Was kann der effiziente Algorithmus dafür sein?