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

Avigation

Answer 1

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";
    }
}

Fireplace

Some of those are built into PHP if I dealt with arrays. See ideone.com/cUaaH for more information. Thank you for your answer though! It will also help, as I didn't know about the range() function. :D – Avigation

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

Lurdan

I've streamlined your example, unicornaddict: ideone.com/cUaaH I actually think this is the right track. All I need to do is get rid of duplicates (like 15789 and 15798, which contain the same digits) by sorting the digits, and checking the sorted array to see if it was returned previously. – Avigation

BAM: ideone.com/Y91ZX Works perfectly, thanks mainly to your answer, unicornaddict! Thank you very much! All in under 20 lines, too. :D – Avigation

Doing the array_sum first in the conditional is probably faster, given the overhead of creating a unique array. – Afterthought

Good idea! It shouldn't be doing costly operations it doesn't need to do. Thanks! – Avigation

Wouldn't iterating to 56789 be sufficient? I believe all numbers above 56789 will be a permutation of a number below 56789. That should cut the iteration length in half. Also, I think the end condition of the for loop should be $i<=, not $i<, you'd want to be sure to test the ending number. – Mercola

Answer 3

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";
        }
}

?>

Afterthought

Answer 4

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?

Deweydewhirst

Answer 5

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.

Dardanus

I suppose one approach would be to find one matching set, then adding/subtracting digits symmetrically to find other sets. – Avigation

Answer 6

I believe this is known as the Subset Sum problem:

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

Spadiceous

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.

Nicaea

Answer 8

Print sum of numbers form an array of n numbers having no duplicate digit in it. For example Input: [100, 213, 414, 555, 62, 321]

Output: 596 ( i.e. 213+62+321 )

Eley

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Ontario