algorithm - 给定分区元素时计算具有 k 个部分的整数分区

Question

我想n用k分区元素计算整数分区。可能的分区元素是通过v具有不同元素的给定向量定义的。可以多次选择分区元素。我怎样才能做到这一点？不遍历n.

例子：

n := 10

k := 3

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

=> 3

标签： algorithmmathdynamic-programmingsubset-suminteger-partition

Answer 1

一种方法是让递归按顺序考虑每个元素。

未记忆的 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]));