Количество комбинаций с постоянной суммой

Question

Предположим, вам даны n списки целых чисел L1,L2,...,Ln и целое число S.

Я ищу способ эффективного подсчета комбинаций индексов j1,j2,...,jn, чтобы L1[j1]+L2[j2]+...+Ln[jn] = S.

В качестве примера возьмем L1=[0,1,1,2], L2=[0,1], L3=[0,1,2,3,3] и S=4. Тогда возможные комбинации

0+1+3
0+1+3
1+0+3
1+0+3
1+1+2
1+0+3
1+0+3
1+1+2
2+0+2
2+1+1

т.е. ответ, который я ищу, это 10.

Answer 1

Эта проблема NP завершена. Вы можете

1) Грубая сила это

или, если у вас есть некоторые дополнительные свойства (например, общая сумма небольшая), вы также можете рассмотреть

2) Используйте динамическое программирование, чтобы получить псевдополиномиальный алгоритм.

Answer 2

Вы можете решить это с DP. Сложность: O (nS).

Count(i,s) = \sum_j=0..s Count(i-1,j) * Number of elements in list i with value (s-j)