Equal Subset Sum Partition Problem - Java Solution

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

In this blog post, we explore the Equal Subset Sum Partition problem, which is a common problem in dynamic programming. The challenge is to determine whether a given array of positive integers can be partitioned into two subsets with equal sums.

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.

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. Calculate the total sum of the array. If the sum is odd, return false, as it cannot be partitioned into two equal subsets.

2. Find if there is a subset with a sum equal to half of the total sum.

3. Use dynamic programming to solve the subset sum problem.

4. Create a boolean 2D array dp where dp[i][j] is true if there is a subset of the first i numbers that adds up to j.

5. Fill the dp table using the given set of numbers.

6. Return the value in dp[n][half of sum].

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] nums1 = {1, 5, 11, 5};
        System.out.println("Can partition: " + canPartition(nums1));

        int[] nums2 = {1, 2, 3, 5};
        System.out.println("Can partition: " + canPartition(nums2));
    }

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

        // If totalSum is odd, cannot partition
        if (totalSum % 2 != 0) return false;

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

        for (int i = 1; i <= nums.length; i++) {
            int curr = nums[i - 1];
            for (int j = 0; j <= subsetSum; j++) {
                if (j < curr) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - curr];
                }
            }
        }
        return dp[nums.length][subsetSum];
    }
}

Output:

Can partition: true
Can partition: false

Explanation:

In the first example, the array [1, 5, 11, 5] can be partitioned into two subsets [1, 5, 5] and [11], both of which sum up to 11. 

The canPartition method first checks if the total sum is even. It then uses dynamic programming to find if there is a subset with a sum equal to half of the total sum. 

The second example returns false as the array [1, 2, 3, 5] cannot be partitioned into subsets with equal sums.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF