編寫一個計算數組中完美總和的函數？

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？）。

祝你好運。