Find all combinations of x numbers where they sum to Y

Question

I'm trying to write this solution in PHP.

Inputs:

number of numbers = x

smallest number = 1

sum of numbers = y

I'm not dealing with very large numbers, largest x is approximatly 50, largest y is approximatly 80.

rules: Within each set of numbers, the number proceeding the previous must be equal to or greater.

For example

x = 3

min = 1

y = 6

solution:
(1,1,4),(1,2,3)

note that (3,2,1) isn't a solution as they are in descending order.

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

This is easily solved via recursion. The time complexity though will be high. For a better (but slightly more complex solution) use dynamic programming.

Here's the idea:

If the size of the set is 1 then the only possible solution is the desired sum.

If the set is larger than one then you can merge a number X between the minimum and the desired sum with a set of numbers which add up to the desired sum minus X.

function tuplesThatSumUpTo($desiredSum, $minimumNumber, $setSize) {
      $tuples = [];  
      if ($setSize <= 1) {
          return [ [ $desiredSum ] ]; //A set of sets of size 1 e.g. a set of the desired sum
      }
      for ($i = $minimumNumber;$i < $desiredSum;$i++) {
          $partial = tuplesThatSumUpTo($desiredSum-$i, $minimumNumber,$setSize-1); 
          $tuples = array_merge($tuples, array_map(function ($tuple) use ($i) {
              $res = array_merge([$i], $tuple);          
              sort($res);
              return $res;
          },$partial));
      }
      return array_unique($tuples,SORT_REGULAR);
}

See it run:

http://sandbox.onlinephpfunctions.com/code/1b0e507f8c2fcf06f4598005bf87ee98ad2505b3

The dynamic programming approach would have you instead hold an array of sets with partial sums and refer back to it to fill in what you need later on.

Find all combinations of x numbers where they sum to Y

Sign up