I want to count the subsets of a with k subset elements which sum to n. The possible subset elements are defined through a given array a with distinct positive elements. Possible subset elements can be just choosen once per subset. How Can i do this? Optimal without iterating through all subsets.
Example:
n := 10
k := 3
a := 1,2,6,7,8
=> 1 ( 1,2,7 )
Make a table A of size (n+1)*(k+1) or map with pair of integers as key.
Entry A[i][j] will contain number of variants to make sum i from j elements
You need to compose value n from k elements, so A[n][k] might be built from A[n-v][k-1] where v is any value from given set.
After filling the table A[n][k] is answer