charany1's blog

Doubt:Subset sum DP solution using 1D array.
By charany1, 9 years ago, In English

Hi there, I came across this dp solution for subset sum problem which uses O(sum) space rather than O(n*sum). The array is filled in a reverse manner i.e. starting from sum.

But I am not able to understand it properly,I know what is happening but not able to make clear sense out of it. Can someone please explain, how its working.

bool is_subset_sum(vector<int>& v,int sum)
{
int n=v.size();
vector<int>dp(sum+1,0);
dp[0]=1; //sum =0 is always attainable.

for(int i=0;i<n;i++)for(int j=sum;j>=v[i];j--)
     dp[j]|=dp[j-v[i]];

return dp[sum];

}
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

First of all, please describe the exact formulation of the version of the subset sum problem that the algorithm intends to solve. If it's something like <<To mark all possible sums with "1"-s and all impossible with "0"-s>>, dp[j]=dp[j-v[i]] should be dp[j]=max(dp[j],dp[j-v[i]])

If you wonder why does the algorithm require reverse order — such order allows to use each value v[i] at most once; using direct order, the same in all other fragments algorithm allows to use arbitrary quantities of each value v[i].

UPD: My mistake at the end of the first paragraph, sorry. dp[j]|=dp[j-v[i]] (with |= operator) looks ok. Thanks to tenshi_kanade's reply below.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It doesn't say dp[j]=dp[j-v[i]], it says dp[j]|=dp[j-v[i]], which is correct.

    → Reply