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

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

Answer 2

The problem is NP-Hard. Even determining if there is ANY subset of the problem that sums to the desired number is NP-Hard (known as the subset sum problem), and there is no known polynomial solution to it.

Thus, you should look for an exponantial solution, such as a backtracking one - generate all possible combinations, and check if they are valid.

You can use trimming to get your search faster (for example, if you generate a partial subset of sum 13, no need to check other subsets which are supersets of this subset, since they will definetly won't lead to a solution.

pseudo code:

findValidSubsets(sum,arr,idx,currSolution):
   if (sum == 0):
       print currSolution
   if (sum < 0): //trim the search, it won't be succesful
       return
   //one possibility: don't take the current candidate
   findPermutations(sum,arr,idx+1,currSolution) 

   //second poassibility: take the current candidate
   currSolution.add(arr[idx])
   findPermutations(sum-arr[idx],arr,idx+1,currSolution)

   //clean up before returning: 
   currSolution.removeLast()

Complexity is O(2^n) - need to generate at worst case all 2^n possible subsets
Invoke with findValidSubsets(desiredSum,myArray,0,[]), where [] is an empty initial list

Answer 3

using dynamic programming you can express solution as

solver(sum,start_index)
     stop_condition_here_when sum <= 0

     r=0
     for  i=start_index ; i < last_iddex :
            r += solver(sum - array[i],i+1)
            r += solver(sum ,i+1)
     return r

And adding extra memositaion would also speedup this program

Answer 4

You can iterate over the length of the set. In each step, check all subsets of length k:

for k = 1 to size(input):
    foreach permutation p of length k:
        if sum(p) == 12:
            bam!