找到在一定范围内加起来为X的N个非重复数的所有可能组合

Question

我几个月来一直试图找到解决方案.这是我的艺术项目.到目前为止,我可以找到部分python和c解决方案,但它们对我的情况没用...我需要一个有效的解决方案,无论是PHP还是Javascript.

这是个问题:

1. 找到N个数字的所有可能组合,应满足以下条件:
   • 数字不会在组合中重复
   • 其他解决方案中的数字不会以不同的顺序重复
   • 只使用整数
2. 在一定范围内的整数
3. 加起来就是X.

例如:

1. 找到3个数字的所有组合
2. 从1-12开始的所有数字
3. 最多15个

计算出的解决方案应吐出:

[1,2,12]
[1,3,11]
[1,4,10]
[1,5,9]
[1,6,8]
[1,7,7] = EXAMPLE OF WRONG OUTPUT, NO REPEATING NUMBERS WITHIN COMBINATION
[1,8,6] = EXAMPLE OF WRONG OUTPUT, NO REPEATING NUMBERS IN OTHER SOLUTIONS (see [1,6,8])
[2,3,10]
[2,4,9]
[2,5,8]
[2,6,7]
[3,4,8]
[3,5,7]
[4,5,6]

显然这很容易在几分钟内手动完成,但我需要计算更大的范围和更多的数字,所以我需要一个简短的脚本来为我做这个...

任何帮助,将不胜感激!

Answer 1

我觉得应对这一挑战的最优雅的方法是通过递归。

function getCombos(target, min, max, n) {
    var arrs = [];
    if (n === 1 && target <= max) {
        arrs.push([target]);
    } else {
        for (var i = min; i < target / n && i <= max; i++) {
            var arrays = getCombos(target - i, i + 1, max, n - 1);
            for (var j = 0; j < arrays.length; j++) {
                var array = arrays[j];
                array.splice(0, 0, i);
                arrs.push(array);
            }
        }
    }
    return arrs;
}

解释

其工作原理是从最小数字开始向上爬升i，作为每个数组中的第一项，并将余数 ( target-i) 传递回递归函数以拆分为n-1多个组件，每次递归调用时最小值都会增加 1。

15 = (1 + 14) = 1 + (2 + 12)
15 = (1 + 14) = 1 + (3 + 11)
15 = (1 + 14) = 1 + (4 + 10)
    ...
15 = (1 + 14) = 1 + (6 + 8)
15 = (2 + 13) = 2 + (3 + 10)
15 = (2 + 13) = 2 + (4 + 9)
    ...
15 = (4 + 11) = 4 + (5 + 6)

请注意，每个数组第一个索引处的数字永远不会超过target/n，其中target是要求和的数字，n是数组中的项目数。（因此，当将 15 分成 3 个分量时，第一列将始终小于 5。）这也适用于其他列，但n随着数组索引的增加而减少 1。知道这一点使我们能够进行递归，而无需在递归函数上添加额外的参数。

工作示例

查看下面的代码片段以了解其实际效果。

function getCombos(target, min, max, n) {
    var arrs = [];
    if (n === 1 && target <= max) {
        arrs.push([target]);
    } else {
        for (var i = min; i < target / n && i <= max; i++) {
            var arrays = getCombos(target - i, i + 1, max, n - 1);
            for (var j = 0; j < arrays.length; j++) {
                var array = arrays[j];
                array.splice(0, 0, i);
                arrs.push(array);
            }
        }
    }
    return arrs;
}

15 = (1 + 14) = 1 + (2 + 12)
15 = (1 + 14) = 1 + (3 + 11)
15 = (1 + 14) = 1 + (4 + 10)
    ...
15 = (1 + 14) = 1 + (6 + 8)
15 = (2 + 13) = 2 + (3 + 10)
15 = (2 + 13) = 2 + (4 + 9)
    ...
15 = (4 + 11) = 4 + (5 + 6)

function getCombos(target, min, max, n) {
    var arrs = [];
    if (n === 1 && target <= max) {
        arrs.push([target]);
    } else {
        for (var i = min; i < target / n && i <= max; i++) {
            var nextTarget = target - i;
            var nextMin = i + 1;
            var arrays = getCombos(nextTarget, nextMin, max, n - 1);
            for (var j = 0; j < arrays.length; j++) {
                var array = arrays[j];
                array.splice(0, 0, i);
                arrs.push(array);
            }
        }
    }
    return arrs;
}

document.getElementById("submit").onclick = function () {
    var target = document.getElementById("target").value;
    var min = document.getElementById("min").value;
    var max = document.getElementById("max").value;
    var n = document.getElementById("n").value;
    var result = getCombos(+target, +min, +max, +n);
    document.getElementById("output").innerHTML = result.join("<br/>");
};