找到总和的数组元素的组合 [英] Find sum from combination of array elements

问题描述

我有一个阵列，如下图所示：

I have an array such as below:

int[] numberArray = {9,2,1,5,6};

我想制定，将采取一个整数作为参数和返回true / false取决于如果参数可以通过任何相加的数字在阵列来实现的方法。

I want to devise a method that will take an integer as an argument and return true/false depending if the argument can be achieved by summing any of the numbers in that array.

public boolean sumCheck (int sum) {
    // ...
}

例如，如果之是 5 ，和检验由于 numberArray将返回true [3] == 5 。如果之是 12 ，和检验，因为<将返回true。 code> numberArray [0] + numberArray [1] + numberArray [2] == 12 。它不会返回true，但是，如果之是 4 ，由于没有结合 numberArray 元素可以归纳到这个号码。

For example, if sum were 5, sumCheck would return true since numberArray[3] == 5. If sum were 12, sumCheck would return true since numberArray[0]+numberArray[1]+numberArray[2] == 12. It would not return true, however, if sum were 4, as no combination of numberArray elements can sum to this number.

推荐答案

这是子集和的问题，这是一个NP完全问题。但是，你可以找到一个伪多项式时间算法（背包的一个变种，使用DP）的维基页面上。

This is the subset sum problem, which is NP-complete. However, you can find a pseudo-polynomial time algorithm (a variant of knapsack, using DP) on the Wiki page.

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