 bemo - 3 years ago 145
PHP Question

# Find all combinations of x numbers where they sum to Y

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. apokryfos

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: