Equal Subset Sum Partition problem

Equal Subset Sum Partition 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.

Problem Identification

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 problem. So I will directly jump to the code.

Method 1: Recursive solution

public class EqualSubsetSumPartitionRecursion {
    private static boolean hasSubsetSum(int[] values, int targetSum, int n) {
        if (targetSum == 0) {
            return true;
        }
        if (n == 0) {
            return false;
        }

        if (values[n - 1] > targetSum) {
            return hasSubsetSum(values, targetSum, n - 1);
        }

        return hasSubsetSum(values, targetSum - values[n - 1], n - 1)
                || hasSubsetSum(values, targetSum, n - 1);
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();

        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = keyboard.nextInt();
        }

        keyboard.close();

        int sum = 0;
        for(int i = 0; i < values.length; i++) {
            sum += values[i];
        }
        System.out.println("Has Equal Subset sum partition: " + hasSubsetSum(values, sum/2, n));
    }
}

Method 2: Dynamic Programming Top down solution (Memoization)

import java.util.Scanner;

public class EqualSubsetSumPartitionTopDown {
    private static Boolean[][] subsetSumMem;

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

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

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

        return subsetSumMem[targetSum][n];
    }

    private static boolean hasSubsetSumMemoized(int[] values, int targetSum, int n) {
        subsetSumMem = new Boolean[targetSum + 1][n + 1];
        for (int s = 0; s <= targetSum; s++) {
            for (int i = 0; i <= n; i++) {
                subsetSumMem[s][i] = null;
            }
        }
        return hasSubsetSumRecur(values, targetSum, n);
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = keyboard.nextInt();
        }
        keyboard.close();

        int sum = 0;
        for(int i = 0; i < values.length; i++) {
            sum += values[i];
        }

        System.out.println("Has Equal Subset sum partition: " + hasSubsetSumMemoized(values, sum/2, n));
    }
}

Method 3: Dynamic Programming Bottom up solution

import java.util.Scanner;

public class EqualSubsetSumPartitionBottomUp {
    private static boolean hasSubsetSum(int[] values, int targetSum) {
        int n = values.length;
        boolean[][] subsetSum = new boolean[targetSum + 1][n + 1];
        subsetSum[0][0] = true;

        for (int i = 1; i <= targetSum; i++) {
            for (int j = 1; j <= n; j++) {
                if (values[j - 1] > i) {
                    subsetSum[i][j] = subsetSum[i][j - 1];
                } else {
                    subsetSum[i][j] = subsetSum[i - values[j - 1]][j - 1] || subsetSum[i][j - 1];
                }
            }
        }

        return subsetSum[targetSum][n];
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = keyboard.nextInt();
        }
        keyboard.close();

        int sum = 0;
        for(int i = 0; i < values.length; i++) {
            sum += values[i];
        }

        System.out.println("Has Equal Subset sum partition: " + hasSubsetSum(values, sum/2));
    }
}

Dynamic Programming