working of Subset sum problem algorithm

Can some one explain me how the subset sum algorithm works? (I saw the algorithm given in Intro to algo by Cormen, but i dont get how exactly it wor开发者_如何转开发ks)

There are 2^n-1 subsets to consider (do not consider the empty set).

On average, each of these 2^n subsets has O(n) elements. So you'll end up doing n*2^n calculations to solve the problem.

There are some speedups possible, but nothing's going to get around the 2^n.

If the absolute size of the elements is small (and discrete), you can start a table indicating whether a particular sum is reachable or not, and adding elements to those "locations" on your table.

First, make the table. It's range will be from the sum of all the negative numbers to the sum of all the positive numbers. (You won't get any sums that are out of the range of the table this way.)

Then, mark "0" as reachable.

Then, for each number, for every reachable number on your table, add the number. So if your first number is 2, then mark "2" as reachable. Then, if you get -3, then mark "-3" and "2-3=-1" as reachable. And so on, until you run out of numbers. Every part of the table that is marked as reachable is indeed reachable; you added some numbers to get there!

The problem description and some algorithms to solve it are on the wikipedia page. Are you confused about the problem itself, or the algorithm to solve it? If the latter, which algorithm are you talking about?