Algorithm for finding a sum within an array? [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

Say you have some array with elements that you know are all positive, and smaller than a number N.

Can someone give me a general, high-level description of an algorithm to find out whether there is some subset within the array in which all the elements add up exactly to N?

It doesn't need to be particularly efficient; the set I'm working with is very small.

Answer 1

If efficiency is not important, an algorithm at a high-level is:

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

Pseudocode. Extremely inefficient.

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)

If you actually implement this make sure numbers is copied (not passed in by ref) for the recursive calls; otherwise it won't work correctly.