Partition Equal Subset Sum - Java Solution

1. Introduction

This blog post addresses the "Partition Equal Subset Sum" problem, a notable challenge in the realm of dynamic programming and combinatorics. The essence of the problem is to determine if a given integer array can be partitioned into two subsets such that the sums of the elements in both subsets are equal.

Problem

Given an integer array nums, the task is to check whether the array can be partitioned into two subsets with equal sums. The goal is to find a subset of nums such that the sum of its elements is equal to the sum of the elements of its complement in nums.

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.

2. Solution Steps

1. Check if the total sum of the array is odd. If it is, return false as it cannot be partitioned into two equal subsets.

2. Use dynamic programming to find if there is a subset with a sum equal to half of the total sum.

3. Create a boolean array dp where dp[i] will be true if there is a subset with sum i.

4. Initialize dp[0] as true and the rest of the array as false.

5. Iterate over each number in the array and update the dp array.

6. For each number, iterate backward from half the total sum to the number, updating dp[j] as true if dp[j - num] is true.

7. Return dp[half of total sum].

3. Code Program

public class PartitionEqualSubsetSum {
    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums)); // Test the function
    }

    // Function to determine if the array can be partitioned into two subsets with equal sums
    public static boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // Check if total sum is odd
        if (totalSum % 2 != 0) {
            return false;
        }

        int subsetSum = totalSum / 2;
        boolean[] dp = new boolean[subsetSum + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = subsetSum; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[subsetSum];
    }
}

Output:

true

Explanation:

1. canPartition: This function evaluates whether the given array nums can be partitioned into two subsets with equal sums.

2. It calculates the total sum of the array and checks if it's odd. If the sum is odd, it's not possible to partition the array, and the function returns false.

3. The function then initializes a boolean dynamic programming array dp. dp[i] indicates whether there's a subset with a sum equal to i.

4. It iterates through each number and updates the dp array, checking if a subset sum equal to half the total sum can be formed.

5. The function returns the value of dp[subsetSum], which indicates whether such a partition is possible.

6. This approach uses dynamic programming to build up the solution, avoiding redundant calculations and efficiently determining the possibility of partitioning the array.