Подсчет подмножеств, состоящих строго из k элементов

Question

Я хочу посчитать подмножества a с k элементами подмножеств, которые составляют n. Возможные элементы подмножества определяются через данный массив a с различными положительными элементами. Возможные элементы подмножества могут быть выбраны один раз для каждого подмножества. Как я могу это сделать? Оптимально без перебора всех подмножеств.

Пример:

n := 10

k := 3

a := 1,2,6,7,8

=> 1 ( 1,2,7 )

Answer 1

Создайте таблицу A размера (n+1)*(k+1) или карту с парой целых чисел в качестве ключа.

Запись A[i][j] будет содержать количество вариантов для суммирования i из j элементов

Вам необходимо составить значение n из k элементов, поэтому A[n][k] может быть построено из A[n-v][k-1], где v - любое значение из данного набора.

После заполнения таблицы A[n][k] ответ