查找组合（S）元素（S）之和的数组，其总和等于给定数 [英] Find combination(s) sum of element(s) in array whose sum equal to a given number

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/12807855/algorithm-extract-subset-based-on-property-sum">Algorithm:提取子集基于财产总和

在简单情况下，我们有一个数组：

in the simple case we have an array:

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

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

和我们想知道所有组合包含在该数组元素的总和来获得的 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

所以，我们如何能做到这一点的BASIC或PHP？也许伪code第一; - 。）

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

我一直在寻找，但没有刚与元素的predetermined号的组合。

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

推荐答案

现在的问题是 NP难。即使确定是否有求和到所需数目的问题的任意子集是NP硬（称为子集总和问题的），并且没有已知的多项式的解决它。

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.

因此​​，你应该寻找一个exponantial的解决方案，如回溯1 - 生成所有可能的组合，并检查它们是否有效

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

您可以用修剪，让您更快的搜索（例如，如果产生一笔13的部分子集，无需检查其他子集这是该子集的超集，因为它们将definetly不会导致解决方案

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.

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

复杂性是 O（2 ^ n）的 - 需要产生在最坏情况下，所有2 ^ n个可能的子集
调用与 findValidSubsets（desiredSum，myArray的，0，[]），其中 [] 是一个空的初始清单

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

这篇关于查找组合（S）元素（S）之和的数组，其总和等于给定数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！