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" />

Answer 2

Here's a slightly optimized solution. By iterating from largest to smallest in the range, it becomes pretty easy to skip all the possibilities that are too large.

function combos(size, start, end, total, solution) {  
    var solutions = [];
    solution = solution || [];
    if (size === 1) {        
        if (start <= total && end >= total) {            
            solutions.push(solution.concat([total]));
        }
        return solutions;
    } else {
        while (end > start) {
            var newTotal = total - end;                    
            solutions = solutions.concat(
                combos(
                    size - 1, 
                    start, 
                    Math.min(end - 1, newTotal), 
                    newTotal, 
                    solution.concat([end])
                )
            );   
            end--;
        }
        return solutions;
    }
}

Answer 3

Below is a recursive function that does what you want.

For your example, you would call it like this:

combos(3, 1, 12, 15);

The additional function parameters (a, running, current) keep track of the current state and can be ignored:

var arr= [];

function combos(num, min, max, sum, a, running, current) {
  var i;

  a= a || [];
  running= running || 0;
  current= current || min;

  for(i = current ; i <= max ; i++) {
    if(num===1) {
      if(i+running===sum) {
        arr.push(a.concat(i));
      }
    }
    else {
      combos(num-1, min, max, sum, a.concat(i), i+running, i+1);
    }
  }
};

Fiddle

Answer 4

Might not be efficient for large numbers, but using 3 nested for() loops you can do -

$t=20; // up to X
$s=$t-3; // sets inner loop max
$r=$t/3; // sets middle loop max
$q=$r-1; // sets outer loop max
$results= array(); // array to hold results

for($x=1;$x<=$q;$x++){

    for($y=($x+1);$y<=$r;$y++){

        for($z=($x+2);$z<=$s;$z++){

            // if sum == max && none are the same value
            if(($x+$y+$z)==$t && ($x!=$y && $x!=$z && $y!=$z)){
                $results[]=array($x,$y,$z);

            }

        }
    }
}

Answer 5

If you generate the lists in ascending order, you will avoid both kinds of repetition.

An easy recursive solution consists of selecting each possible first element, and then recursively calling the generator requesting the possible continuations: that is, the continuations are restricted to having one fewer element, to starting with a value greater than the chosen element, and summing to the desired sum minus the chosen element.

 Partitions(min, size, total):
   if size is 1:
     if total < min: return nothing
     else return the list [total]

   for each value i between min and total:
     get the set of lists Partitions(i+1, size-1, total-i)
     add i to the beginning of each list
   return all the lists. 

The above can be improved by not letting i get beyond the largest practical value, or at least beyond a conservative estimate. Alternatively, you can stop incrementing i after a recursive call returns an empty set.