Detecting if integer can be written as sum of given integers

algorithm, php

Solution

This is another Python solution, but hopefully it's easy for you to convert to PHP (I would do it myself, but I'm no PHP expert - I'm sure you could do a better job of it). I've tried not to use any advanced Python funcitons, so that it is easier for non-Python readers to understand, but if some Python syntax is not clear, please just ask.

allowed = [3, 5, 6, 9, 10]
n = 28

solutions = [ None ] * (n + 1)
solutions[0] = []

for i in range(n + 1):
    if solutions[i] is None: continue
    for a in allowed:
        if i + a > n: continue
        if solutions[i + a] is None or len(solutions[i]) + 1 < len(solutions[i + a]):
            solutions[i + a] = solutions[i] + [a]

print solutions[28]

It works by starting from 0 and building up to the desired number, keeping a cache of the shortest solution seen so far for each possible total. It has a running time of O(n * a), where a is the number of different allowed values.

By the way, your answer to n=28 is wrong. It should be [9, 9, 10].

Update: here's my attempt at a PHP solution:

<?php
$allowed = array(3, 5, 6, 9, 10);
$n = 28;

$solutions = array();
$solutions[0] = array();

foreach (range(0, $n) as $i) {
    if (is_null($solutions[$i])) continue;
    foreach ($allowed as $a) {
        if ($i + $a > $n) continue;
        if (is_null($solutions[$i + $a]) ||
            sizeof($solutions[$i]) + 1 < sizeof($solutions[$i + $a])) {
            $solutions[$i + $a] = array_merge($solutions[$i], array($a));
        }
    }
}

var_dump($solutions[$n]);
?>

It gives the right answer, but please be aware that I'm not a professional PHP coder - I just looked up the equivalent functions in the PHP documentation.

Problem

Original source