Explore our sites

Stack Exchange
tour help careers 2.0
Take the tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote -1 down vote favorite

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.

share|improve this question
 
What have you tried so far? –  Ashwin Mukhija Feb 17 at 4:03
add comment

closed as not a real question by Mitch Wheat, gnat, Aleksander Blomskøld, EdChum, Phil Feb 17 at 11:03

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.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 1 down vote accepted

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
share|improve this answer
add comment
up vote 1 down vote

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.