Skip to main content

Partition Equal Subset Sum

Problem​

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Examples​

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.

Constraints​

  • 1≤nums.length≤2001 \leq \text{nums.length} \leq 200
  • 1≤nums[i]≤1001 \leq \text{nums}[i] \leq 100

Approach​

The following are the two main steps to solve this problem:

  1. Calculate the sum of the array. If the sum is odd, there cannot be two subsets with an equal sum, so return false.
  2. If the sum of the array elements is even, calculate sum / 2 and find a subset of the array with a sum equal to sum / 2.

The first step is simple. The second step is crucial and can be solved either using recursion or Dynamic Programming.

Solution​

This problem can be solved using dynamic programming. We need to find whether the sum of some elements of the array make it equal to sum / 2; if yes, then we return true, otherwise false.

Code in Different Languages​

C++
using namespace std;

bool isSubsetSum(int arr[], int n, int sum, vector<vector<int>>& dp) {
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;

if (dp[n][sum] != -1)
return dp[n][sum];

if (arr[n - 1] > sum)
return isSubsetSum(arr, n - 1, sum, dp);

return dp[n][sum] = isSubsetSum(arr, n - 1, sum, dp) || isSubsetSum(arr, n - 1, sum - arr[n - 1], dp);
}

bool findPartition(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];

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

vector<vector<int>> dp(n + 1, vector<int>(sum + 1, -1));
return isSubsetSum(arr, n, sum / 2, dp);
}

int main() {
int arr[] = {3, 1, 5, 9, 12};
int n = sizeof(arr) / sizeof(arr[0]);

if (findPartition(arr, n))
cout << "Can be divided into two subsets of equal sum";
else
cout << "Cannot be divided into two subsets of equal sum";

int arr2[] = {3, 1, 5, 9, 14};
int n2 = sizeof(arr2) / sizeof(arr2[0]);

if (findPartition(arr2, n2))
cout << endl << "Can be divided into two subsets of equal sum";
else
cout << endl << "Cannot be divided into two subsets of equal sum";

return 0;
}
Java
import java.util.Arrays;

class PartitionEqualSubsetSum {
static int isSubsetSum(int arr[], int n, int sum, int[][] dp) {
if (sum == 0)
return 1;
if (n == 0 && sum != 0)
return 0;

if (dp[n][sum] != -1)
return dp[n][sum];

if (arr[n - 1] > sum)
return isSubsetSum(arr, n - 1, sum, dp);

if (isSubsetSum(arr, n - 1, sum, dp) != 0 || isSubsetSum(arr, n - 1, sum - arr[n - 1], dp) != 0)
return dp[n][sum] = 1;
return dp[n][sum] = 0;
}

static int findPartition(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];

if (sum % 2 != 0)
return 0;

int dp[][] = new int[n + 1][sum + 1];
for (int[] row : dp)
Arrays.fill(row, -1);

return isSubsetSum(arr, n, sum / 2, dp);
}

public static void main(String[] args) {
int arr[] = {3, 1, 5, 9, 12};
int n = arr.length;

if (findPartition(arr, n) == 1)
System.out.println("Can be divided into two subsets of equal sum");
else
System.out.println("Cannot be divided into two subsets of equal sum");

int arr2[] = {3, 1, 5, 9, 14};
int n2 = arr2.length;

if (findPartition(arr2, n2) == 1)
System.out.println("Can be divided into two subsets of equal sum");
else
System.out.println("Cannot be divided into two subsets of equal sum");
}
}
Python
def isSubsetSum(arr, n, sum, dp):
if sum == 0:
return True
if n == 0 and sum != 0:
return False

if dp[n][sum] != -1:
return dp[n][sum]

if arr[n - 1] > sum:
return isSubsetSum(arr, n - 1, sum, dp)

dp[n][sum] = isSubsetSum(arr, n - 1, sum, dp) or isSubsetSum(arr, n - 1, sum - arr[n - 1], dp)
return dp[n][sum]

def findPartition(arr, n):
sum = 0
for i in range(n):
sum += arr[i]

if sum % 2 != 0:
return False

dp = [[-1] * (sum + 1) for _ in range(n + 1)]
return isSubsetSum(arr, n, sum // 2, dp)

arr = [3, 1, 5, 9, 12]
n = len(arr)

if findPartition(arr, n):
print("Can be divided into two subsets of equal sum")
else:
print("Cannot be divided into two subsets of equal sum")

arr2 = [3, 1, 5, 9, 14]
n2 = len(arr2)

if findPartition(arr2, n2):
print("Can be divided into two subsets of equal sum")
else:
print("Cannot be divided into two subsets of equal sum")

Complexity Analysis​

Time Complexity: O(sum×N)O(\text{sum} \times N)​

Reason: The maximum iterations possible are sum * N.

Space Complexity: O(sum×N)O(\text{sum} \times N)​

Reason: We are using an extra array for dp.

References​

  • LeetCode Problem: Partition Equal Subset Sum