在數組中找到總和的算法？

Question

假設你有一些元素，你知道這些元素都是正數，並且小於一個數字N.

有人可以給我一個算法的一般高級描述，以確定是否有一個子集所有元素都加到N的數組？

它不需要特別有效;我正在使用的集合非常小。

Answer 1

如果效率不重要，在一個高層次的算法是：

input: array A[1..K] of positive numbers, positive N 

    for each subset S of { 1..K } 
     sum = 0 
     for each i in S 
      sum = sum + A[i] 
     end 
     if (sum equals N) return true 
    end 
    return false 

Answer 2

僞代碼。非常低效。

if empty(numbers) return false 
return hasSumSubset(numbers, N) 

boolean hasSumSubset(numbers[], N): 
    p = pop(numbers) 
    if empty(numbers) return N == p 
    return hasSumSubset(numbers, N-p) or hasSumSubset(numbers, N) 

如果你真的實現這個確保numbers被複制（不是由參傳遞）的遞歸調用;否則它將無法正常工作。