Найти сумму от комбинации элементов массива

Question

у меня есть массив таким образом, как показано ниже:

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

Я хочу разработать метод, который будет принимать целое число в качестве аргумента и возвращает истину/ложь в зависимости, если аргумент может быть достигается суммированием любого из чисел в этом массиве.

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

Например, если sum были 5, sumCheck вернется верно, так как numberArray[3] == 5. Если sum были 12, sumCheck вернётся с numberArray[0]+numberArray[1]+numberArray[2] == 12. Однако это не вернет истину, если sum были 4, так как никакая комбинация из numberArray элементов не может суммироваться с этим числом.

Answer 1

Это проблема subset sum, которая NP-complete. Тем не менее, вы можете найти псевдополиномиальный алгоритм времени (вариант рюкзака, используя DP) на странице Wiki.

Answer 2

Check http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/..it объясняет вашу проблему прекрасным образом. Первая грубая сила, тогда есть решение dp.