查找数组中元素总和的组合,其总和等于给定数字

Question

可能重复:
算法:基于属性和提取子集

在简单的情况下,我们有一个数组:

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

我们想知道所有组合中包含的数组总和得到12.

在这种情况下,我们将得到四种组合:

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

那么,我们怎样才能在BASIC或PHP中做到这一点？也许伪代码首先;-).

我一直在寻找,但只有预定数量的元素组合.

Answer 1

你可以试试

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

输出

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)

使用的功能

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

问题是NP-Hard.甚至确定是否存在与所需数量相加的问题的任何子集是NP-Hard(称为子集和问题),并且没有已知的多项式解.

因此,您应该寻找一种指数解决方案,例如回溯方法 - 生成所有可能的组合,并检查它们是否有效.

您可以使用修剪来加快搜索速度(例如,如果生成和13的部分子集,则无需检查作为此子集的超集的其他子集,因为它们肯定不会导致解决方案.

伪代码:

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()

复杂性是O(2^n)- 需要在最坏的情况下生成所有2 ^ n个可能的子集
调用findValidSubsets(desiredSum,myArray,0,[]),其中[]是空的初始列表