find all possible combinations of N non-repeating numbers within a certain range that add up to X

Question

i have been trying to find a solution to this for several months now. it is for an art project of mine. so far i could find partial python and c solutions, but they are of no use for my case... i need a working solution either in PHP or Javascript.

this is the question:

1. find all possible combinations of N numbers, the following should be satisfied:
   • numbers are not repeated within a combination
   • numbers are not repeated in other solutions in different order
   • only whole numbers are being used
2. within a certain range of whole numbers
3. that add up to X

for example:

1. find all combinations of 3 numbers
2. within all numbers from 1-12
3. that add up to 15

the computed solution should spit out:

[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]

obviously that was easy to do in a couple of minutes by hand, but i need to calculate a much bigger range and much more numbers, so i need a short script to do this for me...

any help would be appreciated!

Answer 1

I feel like the most elegant way to handle this challenge is via recursion.

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;
}

Explanation

This works by climbing up from the minimum number i as the first item in each array, and passing the remainder (target-i) back into the recursive function to be split into n-1 components, with the minimum increased by one with each recursive call.

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)

Note that the numbers at the first index of each array will never exceed target/n, where target is the number you're summing to, and n is the number of items in the array. (So when splitting 15 into 3 components, the first column will always be less than 5.) This holds true for the other columns as well, but n is reduced by 1 as the index of the array climbs. Knowing this allows us to recurse without requiring extra parameters on our recursive function.

Working Example

Check out the snippet below to see it in action.

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/>");
};

.table {
    display:table;
    table-layout:fixed;
    width:100%;
}
.table-row {
    display:table-row;
}
.cell {
    display:table-cell;
}

<div class="table">
    <div class="table-row">
        <div class="cell">Target:</div>
        <div class="cell">
            <input id="target" type="text" value=15>
        </div>
        <div class="cell">n:</div>
        <div class="cell">
            <input id="n" type="text" value=3>
        </div>
    </div>
    <div class="table-row">
        <div class="cell">Min:</div>
        <div class="cell">
            <input id="min" type="text" value=1>
        </div>
        <div class="cell">Max:</div>
        <div class="cell">
            <input id="max" type="text" value=12>
        </div>
    </div>
</div>
<input id="submit" type="button" value="submit" />
<div id="output" />