How would I find all sets of N single-digit, non-repeating numbers that add up to a given sum in PHP?

Question

Let's say I want to find all sets of 5 single-digit, non-repeating numbers that add up to 30... I'd end up with [9,8,7,5,1], [9,8,7,4,2], [9,8,6,4,3], [9,8,6,5,2], [9,7,6,5,3], and [8,7,6,5,4]. Each of those sets contains 5 non-repeating digits that add up to 30, the given sum.

Any help would be greatly appreciated. Even just a starting point for me to use would be awesome.

I came up with one method, which seems like a long way of going about it: get all unique 5-digit numbers (12345, 12346, 12347, etc.), add up the digits, and see if it equals the given sum (e.g. 30). If it does, add it to the list of possible matching sets.

I'm doing this for a personal project, which will help me in solving Kakuro puzzles without actually solving the whole thing at once. Yeah, it may be cheating, but it's... it's not THAT bad... :P

Answer 1

I know there are algorithms for this, and they will probably be provided by other people, but here's one quick simplification you can make: look for all sets of 4 single digits that add up to 21-29 (I'm assuming you're not counting 0 as a digit) and just eliminate the ones for which 30-(the sum) is one of the digits.

If I wanted to try something even quicker, I'd think about starting with 45678 and incrementally changing that by adding 1 to a digit and subtracting 1 from another digit. Not sure how well it'd work in the end, though.

Answer 2

A naive approach would be to increment a variable from 12345 till 98765 and to select it only if it has unique digits and sum of digits is 30:

for($i=12345;$i<98765;$i++) {
    $arr = preg_split('//',strval($i));
    if(count(array_unique($arr)) == count($arr) && array_sum($arr) == 30)
        echo $i."\n";
}

Working example

Answer 3

function sumOfDigits($num) {
    $str = "{$num}";
    $sum = 0;
    for ($i=0;$i<strlen($str);$i++) {
        $sum += (int)substr($str, $i, 1);
    }
    return $sum;
}

function hasDuplicateDigits($num) {
    $str = "{$num}";
    $pieces = array();
    for ($i=0;$i<strlen($str);$i++) {
        $pieces[] = substr($str, $i, 1);
    }
    return (count(array_unique($pieces)) != strlen($str));
}

// if you prefer the opposite function
function hasAllUniqueDigits($num) {
    return (!hasDuplicateDigits($num));
}

$numbers = range(10000, 99999);

foreach ($numbers as $num) {
    if ( !hasDuplicateDigits($num) && (sumOfDigits($num) == 30)) {
        print $num . "\n";
    }
}

Answer 4

This is probably sufficiently fast:

<?php

$digitCount = 5;
$sum = 30;

function getAnswer($b)
{
        $a = "";
        $i = 1;
        while ($b)
        {
                if ($b & 1) $a .= "$i ";

                $b >>= 1;
                ++$i;
        }
        return $a;
}

for ($b = 0; $b < 512; ++$b)
{
        $v = 0;
        $c = 0;
        $i = 1;

        $s = $b;
        while ($s)
        {
                if ($s & 1)
                {
                        if (++$c > $digitCount) continue 2;
                        $v += $i;
                }
                $s >>= 1;
                ++$i;
        }

        if ($c == $digitCount && $v == $sum)
        {
                echo getAnswer($b)."\n";
        }
}

?>

Answer 5

Using Combinations code from here

foreach(new Combinations("123456789", 5) as $p)
    $r[array_sum(str_split($p))] .= "$p ";
print_r($r); 

result

[15] => 12345 
[16] => 12346 
[17] => 12347 12356 
[18] => 12348 12357 12456 
[19] => 12349 12358 12367 12457 13456 
[20] => 12359 12368 12458 12467 13457 23456 
[21] => 12369 12378 12459 12468 12567 13458 13467 23457 
[22] => 12379 12469 12478 12568 13459 13468 13567 23458 23467 
[23] => 12389 12479 12569 12578 13469 13478 13568 14567 23459 23468 23567 
[24] => 12489 12579 12678 13479 13569 13578 14568 23469 23478 23568 24567 
[25] => 12589 12679 13489 13579 13678 14569 14578 23479 23569 23578 24568 34567 
[26] => 12689 13589 13679 14579 14678 23489 23579 23678 24569 24578 34568 
[27] => 12789 13689 14589 14679 15678 23589 23679 24579 24678 34569 34578 
[28] => 13789 14689 15679 23689 24589 24679 25678 34579 34678 
[29] => 14789 15689 23789 24689 25679 34589 34679 35678 
[30] => 15789 24789 25689 34689 35679 45678 
[31] => 16789 25789 34789 35689 45679 
[32] => 26789 35789 45689 
[33] => 36789 45789 
[34] => 46789 
[35] => 56789 

isn't it cute?

Answer 6

I believe this is known as the Subset Sum problem:

http://mathworld.wolfram.com/SubsetSumProblem.html

Answer 7

Let's write f(30,5,1) for the answer to your problem. The 30 indicates the desired sum, the 5 indicates the number of digits which should add to the desired sum, and the 1 indicates the minimal acceptable digit. In this form, you can solve the problem recursively. For example,

f(30,5,b) = sum_{(i = 1..9)} f(30-i,4,i+1)

We are effectively exhausting over the lowest value i occurring in the combination you seek. If you think more carefully about the maximum possible value of i (it can't be too large since it's the minimum of the digits), and add some appropriate bail-out conditions, then you'll have a very fast solution.