DP #7 Partition Equal Subset Sum

Partition Equal Subset Sum

Problem Statement: here

Solution: 

Firstly, if the total sum is odd, we can simply return false.

Also, note that this problem is again a classic knapsack problem. We saw in CF #637D as well. Here we are given a target sum and are asked to pick those elements who sum up exactly to target sum.

So, we will maintain a 2D dp array dp[i][j] will denote true if it possible to generate a sum j using any of the first i integers. 

Transition : dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]] 

Explaination: If we know the answer for i-1 indices, then for ith index it becomes easy to understand. We can either leave the element at current index for contribution to current subset sum or we can use it. If we leave it, then it becomes the responsibility of first i-1 indices to gather the sum j. we know it is nothing but equal to dp[i-1][j]. If we decide to pick the current element, it becomes dp[i-1][j-a[i]] because to get sum of j, now we have a[i] contribution from current index, so we need j-a[i] sum from elements up to previous index.

Base condition : dp[0][0] = true as it is always possible to get zero sum using zero elements.

Implementation:

class Solution { public: bool canPartition(vector<int>& a) { int sum = 0; for(int i: a) sum += i; if (sum&1) return 0; sum /=2; bool dp[a.size()+1][sum+1]; memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i=1;i<=a.size();i++){ for(int j=1;j<=sum;j++){ if(j >= a[i-1]) dp[i][j] = (dp[i-1][j] || dp[i-1][j-a[i-1]]); else dp[i][j] = dp[i-1][j]; } } return dp[a.size()][sum]; } };

Can we optimize it??

Yes, we can!

We do not need 2 dimensions if we watch carefully, our dp is depending only on the previous state and no more information from the past is required to construct the solution for present. We can reduce it to one dimension with a bit of care. The approach is similar to coin change problem for this case.

class Solution { public: bool canPartition(vector<int>& a) { int sum = 0; for(int i: a) sum += i; if (sum&1) return 0; sum /=2; bool dp[sum+1]; memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i=1;i<=a.size();i++){ for(int j=sum;j>=a[i-1];j--){ dp[j] = (dp[j] || dp[j-a[i-1]]); } } return dp[sum]; } };