## 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 .``````

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 = 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));
}
}``````