在数组中找到总和等于给定数字的元素的总和

小编典典

在数组中找到总和等于给定数字的元素的总和

algorithm

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

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

并且我们想知道所有组合，该数组中包含的元素的总和为 12 。

在这种情况下，我们将获得四种组合：

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

那么，如何在BASIC或PHP中做到这一点？也许首先是伪代码；-)。

我一直在寻找，但只是有了预定数量元素的组合。

阅读 574

2020-07-28

共1个答案

小编典典

问题是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,[])，其中[]空的初始列表

2020-07-28