I'm trying to write this solution in PHP.
Inputs:
number of numbers = x
smallest number = 1
sum of numbers = y
x = 3
min = 1
y = 6
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.