javascript - 获得具有特定总和的范围内 n 个数字的所有可能排列的算法

Question

我正在尝试做的事情可以很容易地用一个例子来说明。假设如下:

var minNum = 1;
var maxNum = 30;
var sum = 75;
var amount = 6;

我想得到所有 amount 数字的所有排列，这些排列加起来为 sum 并且 >= minNum && <= maxNum。

例如，如果我要手动创建这些排列，我会这样开始:

30,30,12,1,1,1

30,30,11,2,1,1

30,30,11,1,2,1

30,30,11,1,1,2

30,30,10,3,1,1

30,30,10,2,2,1

等等

这是数学/编程中的已知问题吗？是否有任何算法可以解决它？

提前致谢。

Answer 1

这是一个 JavaScript 解决方案(如果您的环境递归深度限制了您想要的结果数量，您可以将递归转换为显式数组堆栈，将参数压入函数调用并弹出以处理它们):

function partition(n, min, max, parts) { 
  if (n < 0){
    return;
    
  } else if (n == 0) {
    document.getElementById('output').innerHTML += (JSON.stringify(parts)) + '<br>';
    
  } else {
    for (var i=max; i>=min; i--){
      var _parts = parts.slice();
      _parts.push(i);
      
      partition(n-i,min,max,_parts)
    }
  }
}

partition(6,2,4,[])

<pre id="output"></pre>