I've read a few examples of algorithms to solve problems using DP but slightly struggling to see how to apply it to a given, new, problem.

So supposing the problem was: given a set of integers {1,2,3,...,N}

let S(N) be the number of subsets of those integers that add up to N. Each integer, let's call it i, in the subset can only be used once. (This might actually be similar to an existing PE problem but it's not intended to be, I just made it up to test the technique)

So for instance:

S(1)=1 (the set is {1})

S(2)=1 {2}

S(3)=2 {1,2} and {3}

S(6)=4 {1,2,3} , {1,5}, {2,4}, {6}.

S(10)=10 {10}, {1,9}, {2,8}, {3,7}, {4,6}, {1,2,7}, {1,3,6}, {1,4,5}, {2,3,5}, {1,2,3,4}.

So my, obviously currently flawed, process of generating this algorithm was this:

Consider each i. Find the maximum number ('max') that can be created with integers up to i.

So when i=3, max=1+2+3. When i=4, max=10 as we could have a subset of 1+2+3+4. etc.

Add one to to w[j] for each integer j from i to max. Rationale: using i adds one more possibility to the number of ways of creating each j.

And I came up with this:

Code: Select all

```
def S(N):
w = [0]*(N+1); #w[n] = the number of ways of making n
max = 0
for i in range(1, N+1): #i is the next number in the subset
max += i #the max number we can make with numbers up to i
if max>=N:
max = N
for j in range(i, max+1):
w[j]+=1 # using i adds one more possibility to the ways of making j.
return w
print(S(10))
```

{0, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7}

but it should be

{0, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10}

There's obviously some fundamental flaw in this logic but I'm struggling to see what the correction is.

I keep thinking that the flaw is due to miscounting subsets with 3 or more elements in them, which start at S(6). But my algorithm is correct up to

*and including*S(6) - it only starts giving the wrong answer from S(7) on.

It must be something to do with referring back to previous stored values. Can anyone be so kind as to venture a clear explanation of how to modify the algorithm to be correct?