Применяется оригинальный алгоритм динамического программирования с небольшим расширением - в дополнение к запоминанию частичных сумм, вам также необходимо запомнить количество целочисленных значений, используемых для получения сумм.
В исходном алгоритме при условии целевого значениясумма равна M и есть n целых чисел, вы заполняете логический n x M массив A, где A[i,m] - это истина, если сумма m может быть получена путем выбора (любое количество)от первых i+1 целых (при условии индексации от 0).
Вы можете расширить его до трехмерного массива n x M x k, который имеет аналогичное свойство - A[i,m,l] isистина тогда, если сумма m может быть достигнута путем выбора точно l из первых i+1 целых.
Предполагая, что целые числа находятся в массиве j[0..n-1]:
Рекурсивное отношение довольноаналогично - поле A[0,j[0],1] является истинным (вы выбираете j[0], получая сумму j[0] с 1 int (duh)), другие поля в A[0,*,*] являются ложными и производные поля в A[i+1,*,*] из A[i,*,*] такжепохож на оригинальный алгоритм: A[i+1,m,l] верноесли A[i,m,l] верно (если вы можете выбрать m из первых i дюймов, то, очевидно, вы можете выбрать m из первых i+1 дюймов) или если A[i, m - j[i+1], l-1] верно (если вы выберете j[i+1])затем вы увеличиваете сумму на j[i+1], а число целых чисел на 1).
Если k мало, то, очевидно, имеет смысл пропустить всю вышеуказанную часть и просто перебрать все комбинации k целых и проверка их сумм.k<=4 действительно кажется разумным порогом.