1. Introduction

The Partition Problem is a classic optimization problem. Given a set of non-negative integers, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is the same.

2. Program Steps

1. Calculate the total sum of the array.

2. If the total sum is odd, return false, as it’s impossible to split the set into two subsets with equal sum.

3. If the sum is even, check if there’s a subset with a sum equal to half of the total sum.

4. Use dynamic programming to find if a subset with the desired sum exists.

3. Code Program

public class PartitionProblem {

    // Check if there exists a subset with the given sum
    public static boolean subsetSum(int[] arr, int n, int sum) {
        if (sum == 0) {
            return true;
        }

        if (n < 1 || sum < 0) {
            return false;
        }

        boolean[][] dp = new boolean[n + 1][sum + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (arr[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
                }
            }
        }

        return dp[n][sum];
    }

    // Check if array can be partitioned into two subsets with equal sum
    public static boolean partition(int[] arr) {
        int sum = 0;
        for (int value : arr) {
            sum += value;
        }

        if (sum % 2 != 0) {
            return false;
        }

        return subsetSum(arr, arr.length, sum / 2);
    }

    public static void main(String[] args) {
        int[] arr = { 3, 1, 5, 9, 12 };
        if (partition(arr)) {
            System.out.println("Can be divided into two subsets of equal sum");
        } else {
            System.out.println("Can NOT be divided into two subsets of equal sum");
        }
    }
}

Output:

Can be divided into two subsets of equal sum

4. Step By Step Explanation

1. The subsetSum function checks whether a subset with the given sum exists in the array.

2. We initialize a 2D boolean array dp, where dp[i][j] will be true if there exists a subset of the array up to index i with sum equal to j.

3. If the sum of all elements is odd, then we cannot partition the array into two subsets with equal sum.

4. If the total sum is even, we use the subsetSum function to check if there's a subset with a sum equal to half of the total sum.

5. The solution uses dynamic programming to optimize and avoid recomputation.