I want to count the integer partitions of n
with k
partition elements. The possible partition elements are defined through a given vector v
with distinct elements. Partition elements can be choosen more than once. How Can i do this? Optimal without iterating through all integer partitions of n
.
Example:
n := 10
k := 3
v := 1,2,6,7,8
=> 3
One way is to have the recurrence consider each element in order.
Unmemoised JavaScript:
function f(n, k, v, i=0){
if (k == 0)
return n == 0;
if (i == v.length)
return false;
let total = 0
while (k >= 0 && n >= 0){
total = total + f(n, k, v, i+1);
k = k - 1;
n = n - v[i];
}
return total;
}
console.log(f(10, 3, [1,2,6,7,8]));