Find combination(s) sum of element(s) in array whose sum equal to a given number [duplicate]

Question

Possible Duplicate:
Algorithm: Extract subset based on property sum

in the simple case we have an array:

{6, 1, 3, 11, 2, 5,12}

and we want to know all combinations the sum of elements contained in that array to getting 12.

in this case we will get four combinations:

• 12
• 1 + 11
• 6 + 5 + 1
• 1 + 3 + 2 + 6

so, how can we do this in BASIC or PHP?. maybe pseudo-code first ;-).

I've been looking but there just got a combination with a predetermined number of elements.

Answer 1

You can try

echo "<pre>";

$sum = 12 ; //SUM
$array = array(6,1,3,11,2,5,12);
$list = array();

# Extract All Unique Conbinations
extractList($array, $list);

#Filter By SUM = $sum
$list = array_filter($list,function($var) use ($sum) { return(array_sum($var) == $sum);});

#Return Output
var_dump($list);

Output

array
  0 => 
    array
      1 => string '1' (length=1)
      2 => string '2' (length=1)
      3 => string '3' (length=1)
      4 => string '6' (length=1)
  1 => 
    array
      1 => string '1' (length=1)
      2 => string '5' (length=1)
      3 => string '6' (length=1)
  2 => 
    array
      1 => string '1' (length=1)
      2 => string '11' (length=2)
  3 => 
    array
      1 => string '12' (length=2)

Functions Used

function extractList($array, &$list, $temp = array()) {
    if (count($temp) > 0 && ! in_array($temp, $list))
        $list[] = $temp;
    for($i = 0; $i < sizeof($array); $i ++) {
        $copy = $array;
        $elem = array_splice($copy, $i, 1);
        if (sizeof($copy) > 0) {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            extractList($copy, $list, $add);
        } else {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            if (! in_array($temp, $list)) {
                $list[] = $add;
            }
        }
    }
}