Algorithm for finding a sum within an array?

Question

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