Get all the combinations a number can be split into-CodePudding

I have a fixed number (5) and a fixed length (2):

I want to find all the combinations that can sum 50 (this can vary of course).

For example, for 50, and a length of 2, I want to get:

[[1, 49], [2, 48], [3, 47], [4, 46], ...],

For 50 and a length of 4, I want to get:

[[1, 1, 1, 47], [1, 1, 2, 46], [1, 1, 3, 45], [1, 1, 4, 44], ...],

I have no clue how to do this, or whether there's a name in mathematics for this.

This is what I have (doesn't have to use generators):

function getCombinations(array $numbers, int $sum, int $setLength) : \Generator {
    $numbersLowestFirst = $numbers;
    asort($numbersLowestFirst);
    $lowestNumber = 0;
    foreach ($numbersLowestFirst as $number) {
        // array might be associative and we want to preserve the keys
        $lowestNumber = $number;
        break;
    }

    $remainingAmount = $sum - $lowestNumber;
    $remainingNumberofItems = $setLength - 1;

    $possibleItemCombinations = array_pad([$remainingAmount], $remainingNumberofItems, $lowestNumber);

}

CodePudding user response：

I first made it using JS then translated to PHP. See below for a JS demonstration. The idea is as @Barmar said in comments.

Note: There will be duplicates. If you care for that, you should sort each "triplet" and look for duplications. See JS solution for that below.


function getCombinations($sum, $n)
{
    if ($n == 1) {
        return [[$sum]];
    }

    $arr = [];
    for ($i = 0; $i <= $sum / 2; $i  ) {
        $combos = getCombinations($sum - $i, $n - 1);
        foreach ($combos as $combo) {
            $combo[] = $i;
            $arr[] = $combo;
        }
    }
    return ($arr);
}

JS style, it's the same idea only more comfortable to test on browser.

function getCombinations(sum, n) {
  if (n == 1) return [[sum]];

  var arr = []
  for (var i = 0; i <= sum / 2; i  ) {
    var combos = getCombinations(sum - i, n - 1)
    combos.forEach(combo => {
      arr.push([i, ...combo]);
    })
  }

  // removing duplicates
  arr = Object.values(arr.reduce(function(agg, triplet) {
    triplet = triplet.sort();
    agg[""   triplet] = triplet;
    return agg;
  }, {}))

  return arr;
}

console.log(getCombinations(5, 3))