algorithmmathdynamic-programmingsubset-suminteger-partition

Count integer partitions with k parts when partition elements given


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


Solution

  • 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]));