我如何解决这个复杂的 Javascript 算法而不会使它过于复杂？

Question

一个数的和有多少种方法？

来自维基百科：https ://en.wikipedia.org/wiki/Partition_( number_theory)#

在数论和组合学中，正整数 n 的分区，也称为整数分区，是将 n 写成正整数之和的一种方式。仅在被加数的顺序上不同的两个和被认为是相同的分区。如果顺序很重要，那么总和就变成了一个组合。例如，4 可以按五种不同的方式进行分区：

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
Examples
Basic
sum(1) // 1
sum(2) // 2  -> 1+1 , 2
sum(3) // 3 -> 1+1+1, 1+2, 3
sum(4) // 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
sum(5) // 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3

sum(10) // 42
Explosive
sum(50) // 204226
sum(80) // 15796476
sum(100) // 190569292

我的尝试

我试图同时循环遍历两个数组并相互测试它们。由于一些原因，这不起作用（至少以我的方式）。

我的代码：

function sum(num, arr = []) {
  if(num == 0){
    return testNumbers(arr, num);
}
  arr.push(num);
  return sum(num - 1, arr);


function testNumbers(arrr, n){
  let arr2 = [...arrr];
  let count = 0; 

  let calculations = arrr.filter((item)=>{
  return item + arr2.map((a)=>{
     return a;
   }) == n;
    
  })


console.log(calculations);

}


}


console.log(sum(10));

您不需要修复我的代码，因为我认为它无法挽救，但是您如何解决问题？

Answer 1

如果我们将问题视为计算具有给定下界的分区，这实际上是一个相当简单的递归。我们有两个简单的基础情况0和1如果下界比我们的目标数量大于或等于它。否则，我们会以两种方式重复出现，一种是当我们使用该下限时，另一种是当我们不使用时。这是一个版本，lb要使用的数字的下限在哪里：

const count = (n, lb = 1) =>
  lb > n
    ? 0
  : lb == n
    ? 1
  : count (n - lb, lb) + count (n, lb + 1)

这会计算具有给定下限的分区数。所以count(10, 3)会产生5， 中的每个数组一个[[3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]。虽然下限的默认值意味着我们可以只用我们的目标数字来调用它，但如果我们尝试map超过它，就会有潜在的问题。所以最好把它包装在一个单独的函数中，const countPartitions = (n) => count (n, 1)

const count = (n, lb) =>
  lb > n
    ? 0
  : lb == n
    ? 1
  : count (n - lb, lb) + count (n, lb + 1)

const countPartitions = (n) => count (n, 1)

console .log ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10] .map (countPartitions))

但是对于较大的输入，这将非常慢。我的测试100花了 56.3 秒。）如果我们记住中间结果，我们应该加快速度。我们可以手动执行此操作，或者我更喜欢使用备忘录助手：

const memoize = (makeKey, fn) => {
  const memo = {}
  return (...args) => {
    const key = makeKey (...args)
    return memo [key] || (memo [key] = fn (...args))
  }
}

const count = memoize (
  (n, lb) => `${n}~${lb}`, 
  (n, lb) => 
    lb > n
      ? 0
    : lb == n
      ? 1
    : count (n - lb, lb) + count (n, lb + 1)
)

const countPartitions = (n) => count (n, 1)

console .log (countPartitions (100))

在我的测试中，这现在需要 20 毫秒。