A Variation on the Knapsack Problem: Solving the Partition Equal Subset Sum in Java Using Dynamic Programming

The Partition Equal Subset Sum is an interesting problem that builds upon concepts from the classic 0/1 Knapsack Problem. In this article, we‘ll dive into how to solve Partition Equal Subset Sum efficiently using dynamic programming in Java.

Problem Statement

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

For example:

• nums = [1,5,11,5] => true (subsets [1,5,5] and [11] have equal sum of 11)
• nums = [1,2,3,5] => false (array cannot be partitioned into equal sum subsets)

Brute Force Approach

Before jumping into the efficient solution, let‘s consider a straightforward recursive brute force approach. The idea is to generate all possible subsets and check if any two have an equal sum that is half of the total sum of the array.

To generate subsets, at each element, we have two choices – include the current element in the subset or exclude it. We can represent this as a recursive tree.

Here‘s what the brute force code might look like in Java:

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // if totalSum is odd, cannot partition into equal subsets
        if (totalSum % 2 != 0) {
            return false;
        }

        return canPartitionRecur(nums, 0, totalSum/2);
    }

    private boolean canPartitionRecur(int[] nums, int index, int subsetSum) {
        // base cases
        if (subsetSum == 0) {
            return true;
        }
        if (index == nums.length || subsetSum < 0) {
            return false; 
        }

        // either include current element in subset or don‘t include it
        return canPartitionRecur(nums, index + 1, subsetSum - nums[index]) 
            || canPartitionRecur(nums, index + 1, subsetSum);
    }
}

The time complexity of this approach is O(2^n) since we generate all 2^n subsets. The space complexity is O(n) for the recursion stack. Clearly this is not feasible for larger inputs due to the exponential time. Let‘s see how we can do better.

Dynamic Programming Approach

To solve Partition Equal Subset Sum efficiently, we can use dynamic programming. The problem has an optimal substructure and overlapping subproblems, which makes it a good candidate for DP.

The idea is to build a 2D boolean table table where table[i][j] represents whether a subset with sum j can be attained using elements up to index i (first i elements).

We‘ll build the table in a bottom-up manner. First, let‘s consider some base cases:

1. table[0][0] = true. The empty set {} has a sum of 0.
2. table[0][j>0] = false. The empty set cannot have a positive sum.

Then, for each element at index i from 1 to n:

1. If nums[i] > j (current element is greater than current sum j), we cannot include this element. Thus, table[i][j] = table[i-1][j] (without including nums[i]).

2. If nums[i] <= j, we have two options: include nums[i] in the subset OR not include it.

   • If we include nums[i], we need to see if a subset sum of j-nums[i] can be formed from the first i-1 elements. This subproblem is solved by table[i-1][j-nums[i]].
   • If we don‘t include nums[i], we rely on whether a subset sum of j can be formed from first i-1 elements. This subproblem is solved by table[i-1][j].

Therefore, table[i][j] = table[i-1][j-nums[i]] OR table[i-1][j].

At the end, table[n][totalSum/2] will tell us if the array can be partitioned into two subsets with equal sum.

Java Code

Here‘s the Java code for the dynamic programming solution:

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // if totalSum is odd, cannot partition into equal subsets
        if (totalSum % 2 != 0) {
            return false;
        }

        int subsetSum = totalSum / 2;
        int n = nums.length;
        boolean[][] table = new boolean[n+1][subsetSum+1];

        // empty set can always have 0 sum
        table[0][0] = true;

        for (int i = 1; i <= n; i++) {
            int curr = nums[i-1];
            for (int j = 0; j <= subsetSum; j++) {
                if (j < curr) {
                    table[i][j] = table[i-1][j];
                }
                else {
                    table[i][j] = table[i-1][j] || table[i-1][j-curr];
                }
            }
        }

        return table[n][subsetSum];
    }
}

The time and space complexity of this approach is O(n*sum) where n is the number of elements and sum is the total sum of the array. Even though this is still pseudo-polynomial due to the sum term, it is much more efficient than the exponential brute force solution.

Example Walkthrough

Let‘s walk through an example with the array nums = [1,5,11,5].

First, we calculate the totalSum which is 22. Since 22 is even, we can proceed with building our DP table for subsetSum = 11.

We start by initializing the base case of an empty set in table[0][0]:

Then, we iterate through the array. First with element 1:

Next with element 5:

Then with element 11:

Finally with the last element 5:

Since table[4][11] = true, we return true. The array can be partitioned into subsets [1,5,5] and [11], each with a sum of 11.

Optimizations

A couple optimizations can be made to the above solution:

1. If the total sum is odd, we can return false right away since the array cannot be partitioned into two subsets with equal sum.

2. Instead of a 2D table, a 1D table can be used to optimize space. The idea is that table[j] represents whether a subset sum j can be formed from the first i elements. We update the table from right to left for each element to avoid using the same element multiple times. This reduces the space complexity to O(sum).

Relationship to Other Problems

Partition Equal Subset Sum is related to a few other classic problems:

• Subset Sum: Given an array and a target sum, determine if any subset of the array has a sum equal to the target. This is a more general problem. Partition Equal Subset Sum basically asks if there is a subset with sum equal to totalSum/2.

• 0/1 Knapsack: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In Partition Equal Subset Sum, we can think of each number as an item with weight equal to its value. We want to find if we can fill a knapsack with capacity totalSum/2.

Understanding the underlying patterns in these problems allows us to develop a general intuition for solving similar problems.

Conclusion

In this article, we explored how to solve the Partition Equal Subset Sum problem using dynamic programming. We first considered a brute force approach and then optimized it by building a DP table.

The key takeaway is to think about how to break down a problem into smaller subproblems that can be reused. Identifying the problem structure and overlapping subproblems is crucial for designing a DP solution.

I hope this article provided you with a solid understanding of Partition Equal Subset Sum and dynamic programming concepts. The problem-solving thought process can be applied to many other problems as well. Happy coding!