sum - 在数组中求和的算法？

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为递归调用复制（而不是通过 ref 传入）；否则它将无法正常工作。