The operation of the summation algorithm of the sum of the subset

Question

Can someone explain to me how the summation algorithm works? (I saw the algorithm given in Intro for almen from Cormen, but I don’t understand how it works)

Answer 1

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 decide to do n * 2 ^ n calculations to solve the problem.

Some accelerations are possible, but nothing happens around 2 ^ n.

If the absolute size of the elements is small (and discrete), you can run a table indicating whether a particular amount is achievable or not, and adding elements to these “locations” in your table.

Make a table first. This range will be from the sum of all negative numbers to the sum of all positive numbers. (This way you won’t get any amounts outside the table.)

Then mark "0" available.

Then, for each number, for each available number in your table, add a number. Therefore, if your first number is 2, then mark “2” as reachable. Then, if you get -3, mark "-3" and "2-3 = -1" as achievable. And so on, until you finish the numbers. Each part of the table designated as achievable is truly achievable; You added some numbers to get there!

Answer 2

A description of the problem and some algorithms for solving it can be found on the wikipedia page. Are you confused by the problem itself or the algorithm for solving it? If the latter, what algorithm are you talking about?