时间戳

首页 > 解决方案 > 获取 N 大小的数字，加起来等于数字 X

javascript - 获取 N 大小的数字，加起来等于数字 X

问题描述

我的问题可能看起来像是重复的，但我找不到如何在 vanilla javascript 中执行此操作。（我在这里在 python 中找到了答案。）

所以基本上我想得到一个所有可能的数字组合的列表，这些组合总和为所需的数字。

例如：

function sum_to_n(n,size){}

x = sum_to_n(6,3)
// [6,0,0] [5,1,0] [4,2,0] [4,1,1] [3,3,0] [3,2,1] [2,2,2]

到目前为止，这是我能做的：

function sum_to_n(n, size, sum=[], limit) {
  if (size === 1) {
    sum.push(n)
    return sum
  }

  if (!limit) {
    limit = n
  }

  let start = Math.min(n, limit)
  let stop = Math.ceil(n/size) - 1

  for (let i = start; i > stop; i--) {
    let tmp = [...sum];
    tmp.push(i)
    let combination = sum_to_n(n-i, size - 1, tmp, i)
    if (combination) {
      console.log(combination) // this work
    }
  }
}

// I don't know how to make this work
let x = sum_to_n(6, 3)
// or maybe this
for (let y in sum_to_n(6,3)) {
  console.log(y)
}

标签： javascriptrecursion

解决方案

'use strict';

function _sumToN(n, size, acc = [], solutions = []) {
  if (size === 0) {
    const sum = acc.reduce((sum, num) => sum + num);

    return sum === n ? solutions.concat([acc]) : solutions;
  }

  for (let i = 0; i <= n; ++i)
    solutions = _sumToN(n, size - 1, acc.concat(i), solutions);

  return solutions;
}

function sumToN(n, size) {
  return _sumToN(n, size);
}

console.log(sumToN(6, 3));

上面使用了一个驱动程序，_sumToN它接受一个额外的acc累加器数组，以及一个solutions最终将保存所有解决方案的数组。它迭代如下：

0 0 0
0 0 1
0 0 2
...
0 0 6
...
6 6 6

并在它们总和为 时保存解决方案n。当然可以进行优化，但希望这个微不足道的实现会有所帮助。

推荐阅读