Partition Equal Subset Sum

Problem

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.

Examples

Example 1

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

Example 2

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Solution

Let’s say that the array nums can be broken down into two subsets S1 and S2 of equal sums. We can observe the following things

// Sum of all the numbers in subset S1 + Sum of all the numbers in subset S2 = Sum of all the numbers in the array
Sum(S1) + Sum(S2) = Sum(nums)

// If Sum(S1) and Sum(S2) is equal
2*Sum(S1) = Sum(nums)

Sum(S1) = Sum(nums)/2

The problem reduces to finding a subset of sum Sum(nums)/2 in the array. If we can find a subset of sum Sum(nums)/2 then we can definitely partition the array into two subsets of equal sums.

Note that I have already explained the solution approach for the [Subset Sum 1 - Is there a subset?](subset-sum-1-is-there-a-subset-). So I will directly jump to the code.

Method 1 - Recursive Solution

Code

Java

class Solution {
	public boolean canPartition(int[] nums) {
		int sum = Arrays.stream(nums).sum();
		// if sum is odd, we cant divide in equal 2 halfs
		if (sum % 2 == 1) {
			return false;
		}

		return dfs(nums, sum / 2, nums.length - 1);
	}

	private boolean dfs(int[] nums, int sum, int n) {
		if (sum == 0) {
			return true;
		}

		if (n == 0) {
			return false;
		}

		if (nums[n - 1] > sum) {
			return dfs(nums, sum, n - 1);
		}

		return dfs(nums, sum - nums[n - 1], n - 1) || dfs(nums, sum, n - 1);
	}
}

Complexity

• ⏰ Time complexity: O(2^n), where n is number of elements in array, as run the DFS to find set of n elements whose sum is equal to sum(nums)/2.
• 🧺 Space complexity: O(n) for recursion stack

Method 2 - Dynamic Programming Top Down Solution (Memoization)

Code

Java

class Solution {
    private Boolean[][] dp;
    public boolean canPartition(int[] values, int targetSum, int n) {
        dp = new Boolean[targetSum + 1][n + 1];
        return hasSubsetSumRecur(values, targetSum, n);
    }

    private boolean dfs(int[] values, int targetSum, int n) {
        if (targetSum == 0) {
            return true;
        }
        if (n == 0) {
            return false;
        }

        if (subsetSumMem[targetSum][n] != null) {
            return dp[targetSum][n];
        }

        if (values[n - 1] > targetSum) {
            dp[targetSum][n] = hasSubsetSumRecur(values, targetSum, n - 1);
        } else {
            dp[targetSum][n] = hasSubsetSumRecur(values, targetSum - values[n - 1], n - 1)
                    || hasSubsetSumRecur(values, targetSum, n - 1);
        }

        return dp[targetSum][n];
    }


}

Method 3 - Dynamic Programming Bottom up Solution

Code

Java

class Solution {
    private static boolean hasSubsetSum(int[] nums, int targetSum) {
        int n = nums.length;
	    // 
        boolean[][] dp = new boolean[targetSum + 1][n + 1];
        subsetSum[0][0] = true;// without any elements, sum of 0 is easily acheived

        for (int i = 1; i <= targetSum; i++) {
            for (int j = 1; j <= n; j++) {
	            // if number is larger then sum, we skip this number
                if (nums[j - 1] > i) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i - nums[j - 1]][j - 1] || dp[i][j - 1];
                }
            }
        }

        return subsetSum[targetSum][n];
    }

}