Алгоритм суммирования подмножеств с повторением чисел в наборе
У меня есть набор S, содержащий натуральные числа и цель t, которая является числом. я хочу знать
как мы можем найти количество возможных комбинаций этих чисел, которое суммирует до цели t.
Число может быть взято любое количество раз, и любое число может быть взято для получения
сумма равна цели 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
Какой может быть эффективный алгоритм для этого?