编写一个计算数组中完美总和的函数？

Question

完美总和是两个或更多数组元素的总和，其总和等于给定数量。如果找不到，则返回999。

我的方法的签名是：

public static int persfectSum(int arr[], int input) 

例如：

arr={2,3,5,6,8,10} 
input = 10; 

5+2+3= 10 
2+8 = 10 
So, the output is 2; 

Answer 1

它是Subset-Sum problem的变化 - 对所述子集的大小的附加约束（较大然后1） 。

问题是NP-Complete，但对于相对较小的整数可以用Dynamic Programming in pseudo-polynomial time解决。

小阵列可行的一种可能更简单的替代方案是蛮力 - 只需搜索所有可能的子集，然后验证它们是否匹配总和。

我相信这些指南已经足够作为初学者开始编写问题并自行解决问题（HW？）。

祝你好运。