Dynamic Programming — Equal Sum Partition Problem

So the leetcode link for this problem is — https://leetcode.com/problems/partition-equal-subset-sum/ in which the problem states as —

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

So here it basically means we need to divide the input array into two parts whose sum is equal to each other. And also notice each element can be skipped over i.e. if first element is part of partitionA and second element is part of partitionB then third element can be part of partitionA or B wherever it finds its place. That’s how in above example, the last element 5 is part of first partition, not second.

So first condition here is to check that if the totalSum can be divided by 2 then only the partition can happen in two parts for equal sum, otherwise its false.

So the trick here for this problem is, Once we have divided the totalSum of input array by 2, the output of the divison (Let’s call it S). So now the problem reduces into the statement that We are looking for a subset whose sum is equal to given sum S. That’s the exact problem statement of subset sum problem for which I have already posted the solution here — https://mukeshsri.medium.com/dynamic-programming-subset-sum-problem-73f30080d93e. Please visit for checking the underlying approach for solving subset sum problem.

Basically the underlying intuition for building the overlapping subproblems solution is that for each element of the input array, we check if this element value is larger than S (i.e. Target sum). If yes, then we skip that element, otherwise if the element is equal to S, then we make the choice if including the current element or excluding the current element into subset will lead us in finding the subset of given sum.

So moving ahead here for the DP solution based upon subset sum intuition,

public boolean canPartition(int[] nums) {
        int n=nums.length;
        if (n<2) return false;
        
        int totalSum = 0;
        
        for (int i : nums)
            totalSum += i;
        
        if (totalSum%2 != 0) return false;
        
        int sum = totalSum/2;
// Now the problem reduces into subset sum problem. We are finding a subset who sum is equal to sum(totalSum/2). 
   
        boolean dp[][] = new boolean[n+1][sum+1];
        
        for (int i=0; i<=n; i++) {
            for (int j=0; j<=sum; j++) {
                if (i==0 && j==0) dp[i][j] = true; // both sum and input is empty.
                else if (i==0) dp[i][j] = false; // if input size is 0 but sum > 0
                else if (j==0) dp[i][j] = true; // if sum==0 but input size>0.
            }
        }
        
        for (int i=1;i<=n; i++) {
            for (int j=1; j<=sum; j++) {
                if (nums[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j - nums[i-1]] || dp[i-1][j];
                }
            }
        }
        
        return dp[n][sum];
        
    }

So see, This isn’t so difficult once you have studied subset sum problem and understand that underlying intuition. Hope it turned out good for people who hadn’t solved subset sum problem yet. Please let me know if any comments,feedbacks. Highly appreciated. Thanks.