Subset sum leetcode problem states that given an array a[ ] of size n. Check if the array can be divided into two subsets such that the sum of values of one subset is equal to the other subset. Print “Yes” if it’s possible else “No”.
Table of Contents
Example
a[ ] = {2, 3, 5}Yes
Explanation: The sum of the first and second elements equals the third element. Thus, the given array can be divided into two subsets.
a[ ] = {1, 2, 4, 9}No
Explanation: There is no possible combination such that the array can be divided into two subsets, such that they have the equal sum.
Recursive Method
Algorithm
1. Initialize an array a[ ] of size n.
2. Traverse the array and find the sum of all the elements in the given array a[]. Check if sum mod 2 is not 0, return false.
3. Create a function that checks if there is any subset in an array whose sum is equal to half the sum of the full original array.
4. Call this function recursively by including the last element and by excluding the last element.
5. If the sum is zero, return true. Else if the sum is not zero and n is zero, return false.
Implementation for Subset Sum Leetcode
C++ Code for Subset Sum
#include <bits/stdc++.h>
using namespace std;
bool isEqualSum(int a[], int n, int sum){
if(sum == 0)
return true;
if(n == 0 && sum != 0)
return false;
if(a[n-1] > sum)
return isEqualSum(a, n-1, sum);
return isEqualSum(a, n-1, sum) ||
isEqualSum(a, n-1, sum-a[n-1]);
}
bool Partiion(int a[], int n){
int sum = 0;
for(int i=0; i<n; i++)
sum += a[i];
if(sum%2 != 0)
return false;
return isEqualSum (a, n, sum/2);
}
int main(){
int a[] = {2, 3, 5};
int n = sizeof(a)/sizeof(a[0]);
if(Partiion(a, n))
cout << "Yes";
else
cout << "No";
return 0;
}Yes
Java Code for Subset Sum
import java.io.*;
class equalSum{
static boolean isEqualSum(int a[], int n, int sum){
if(sum == 0)
return true;
if(n == 0 && sum != 0)
return false;
if(a[n-1] > sum)
return isEqualSum(a, n-1, sum);
return isEqualSum(a, n-1, sum) ||
isEqualSum(a, n-1, sum-a[n-1]);
}
static boolean Partition (int a[], int n){
int sum = 0;
for(int i = 0; i < n; i++)
sum += a[i];
if (sum%2 != 0)
return false;
return isEqualSum(a, n, sum/2);
}
public static void main (String[] args){
int a[] = {2, 3, 5};
int n = a.length;
if(Partition(a, n) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}Yes
Complexity Analysis for Subset Sum Leetcode
Time Complexity
Since each problem is being divided into two smaller subproblems. That is the algorithm has O(2n) time complexity, where n is the number of integers in the given array a[ ].
Space Complexity
O(1), because we used constant extra space.
Dynamic Programming Method
Algorithm
1. Initialise an array a[ ] of size n.
2. Traverse the array and find the sum of all elements. Check if sum mod 2 is not 0, return false.
3. Create a 2D array.
4. Update the first row as true and the first column of each row as false.
5. Start traversing and update the part[][] as true if the sum of any subset of the original array till j-1 is equal to i. Else false.
6. Return the last boolean value in part.
Implementation for Subset Sum Leetcode
C++ code for Subset Sum
#include <bits/stdc++.h>
using namespace std;
bool Partiion(int a[], int n){
int sum = 0;
int i, j;
for(i=0; i<n; i++)
sum += a[i];
if(sum%2 != 0)
return false;
bool part[sum / 2 + 1][n + 1];
for (i = 0; i <= n; i++)
part[0][i] = true;
for (i = 1; i <= sum/2; i++)
part[i][0] = false;
for(i=1; i<=sum/2; i++){
for(j=1; j<=n; j++){
part[i][j] = part[i][j-1];
if(i >= a[j-1])
part[i][j] = part[i][j] ||
part[i - a[j-1]][j-1];
}
}
return part[sum/2][n];
}
int main(){
int a[] = {2, 3, 5};
int n = sizeof(a)/sizeof(a[0]);
if(Partiion(a, n))
cout << "Yes";
else
cout << "No";
return 0;
}Yes
Java code for Subset Sum
import java.io.*;
class equalSum{
static boolean Partition (int a[], int n){
int sum = 0;
int i, j;
for(i=0; i<n; i++)
sum += a[i];
if(sum%2 != 0)
return false;
boolean part[][]=new boolean[sum/2+1][n+1];
for (i = 0; i <= n; i++)
part[0][i] = true;
for (i = 1; i <= sum/2; i++)
part[i][0] = false;
for(i=1; i<=sum/2; i++){
for(j=1; j<=n; j++){
part[i][j] = part[i][j-1];
if(i >= a[j-1])
part[i][j] = part[i][j] ||
part[i - a[j-1]][j-1];
}
}
return part[sum/2][n];
}
public static void main (String[] args){
int a[] = {2, 3, 5};
int n = a.length;
if(Partition(a, n) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}Yes
Complexity Analysis for Subset Sum Leetcode
Time Complexity
O(sum*n) where n is the number of integers in the given array a[ ] and the sum is the sum of all the elements in the given array a[ ].
Space Complexity
O(sum*n) because we used sum*n extra space.