PHP: Can an array of numbers stack to a number

Question

This is more of a puzzle than anything. I really found a solution, but it is so slow, I thought I lost my internet connection (see below).

Here's the problem:

Let's say I have an array of numbers, for example:

$numbers_array = array(1, 2, 3, 4, 5, 6, 7, 8, 9); 

Let them also say that I have a number of numbers stored in such variables:

 $sum = 15; $sum2 = 24; $sum3 = 400; 

I am trying to create a function that will return true if any of the numbers in $numbers_array can be added together (each of them is used once) to form the sums:

 function is_summable($array_of_nums, $sum_to_check) { //What to put here? } var_dump(is_summable($numbers_array, $sum)); var_dump(is_summable($numbers_array, $sum2)); var_dump(is_summable($numbers_array, $sum3)); 

The above should output:

 bool(true) bool(true) bool(false) 

Since 7 + 8 = 15, 7 + 8 + 9 = 24, but no combination of 1-9 can create 200.

Here is my EXTREMELY slow solution:

 function is_summable($numbers, $sum) { //Sort provided numbers and assign numerical keys. asort($numbers); $numbers = array_values($numbers); //Var for additions and var for number of provided numbers. $total = 0; $numbers_length = count($numbers); //Empty var to fill below. $code = ''; //Loop and add for() loops. for ($i = 0; $i < $numbers_length; $i++) { $code .= 'for ($n' . $i . ' = 0; $n' . $i . ' < ' . $numbers_length . '; $n' . $i . '++) {'; if ($i != 0) { $code .= 'if ($n' . $i . ' != $n' . ($i - 1) . ') {'; } $code .= '$total += intval($numbers[$n' . $i . ']);'; $code .= 'if ($total == $sum) {'; $code .= 'return true;'; $code .= '}'; } //Add ending bracket for for() loops above. for ($l = 0; $l < $numbers_length; $l++) { $code .= '$total -= intval($numbers[$n' . $i . ']);'; if ($l != 0) { $code .= '}'; } $code .= '}'; } //Finally, eval the code. eval($code); //If "true" not returned above, return false. return false; } $num_arr = array(1,2,3,4,5,6,7,8,9); var_dump(is_summable($num_arr, 24)); 

http://pastebin.com/1nawuwXK

As always, help is appreciated!

Answer 1

Your problem is actually a standard algorithmic problem (since John mentioned the knapsack problem), more specifically the Subset Sum Problem . It can be solved in polynomial time (look at the wiki page ).

pseudo code:

 initialize a list S to contain one element 0. for each i from 1 to N do let T be a list consisting of xi + y, for all y in S let U be the union of T and S sort U make S empty let y be the smallest element of U add y to S for each element z of U in increasing order do //trim the list by eliminating numbers close to one another //and throw out elements greater than s if y + cs/N < z ≤ s, set y = z and add z to S if S contains a number between (1 − c)s and s, output yes, otherwise no