CODEWITHSUNDEEP
algorithm
J.doe
J.doe

Reputation: 373

Subset sum Prob. - Recursive step

This question is about the Subset Sum problem with positive integers

Assume that we have n positive integers a[1],a[2],...,a[n] and we are given an Integer M. We want to know if there is a subset of integers with sum M.

Set v[i,m] = 1 if there is a subset of a[1], a[2], ... , a[i] with sum m and v[i,m] = 0 otherwise.

if v[i,m] = 1 it must be either because we can get m just by using the numbers a[1], a[2], ... , a[i-1] or because we can get the sum m - a[i] by using the same numbers. We get the recursion.

lets take an example with the n positive integers to be : [3, 2, 7, 1] and M = 6 , then we have a subset [3,2,1] 

just by using the numbers a[1], a[2], ... , a[i-1]

So that means we could remove the integer 1 and so that 3+2=6 , which doesn't hold , so we move on to the next condition:

sum m - a[i] by using the same numbers

Ofcourse 3+2 = 6-1 - well this condition should always hold.

I am missing something in my understanding of what they are trying to say, could someone fill in?

Upvotes: 1

Views: 41

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Hypothetical

Suppose we know there is a subset of a[1],a[2],...,a[i] with sum m.

Ask yourself whether the subset includes a[i] or not.

If answer is No

Then the same subset can be used to show there is a subset of a[1],a[2],...,a[i-1] with sum m.

If answer is Yes

Then we know that there is a subset (with x,y < i) such that a[x]+a[y]+...+a[i] = m.

Therefore a[x]+a[y]+... = m-a[i]

Therefore there is a subset of a[1],...,a[i-1] with sum m-a[i]

Conclusion

So we have proved that if v[i,m] is equal to 1, then one or other condition must hold. (It is also possible for both conditions to hold.)

Alternative perspective

It may seem more natural to look at this constructively.

Think of all values you can make as a subset of a[1],..,a[i-1]. In your example [3,2,7] can make all the values [0,2,3,5,7,10,12,13].

Then consider what values we can make if we also can include a[i]. This will be the original set of values [0,2,3,5,7,10,12,13] intersected with the set of values with a[i] added [0+1,2+1,3+1,5+1,7+1,10+1,12+1,13+1].

So a value m will be in the new set either if it was in the old set, or if m-a[i] was in the old set.

Upvotes: 1

Related Questions