Subset Sum Problem using Memoization
As seen in the previous recursion method, each state of the solution can be uniquely identified using two variables – the index and the remaining sum. So create a 2D array to store the value of each state to avoid recalculation of the same state.
Below is the implementation of the above approach:
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Taking the matrix as globally
int tab[2000][2000];
// Check if possible subset with
// given sum is possible or not
int subsetSum(int a[], int n, int sum)
{
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1][sum] != -1)
return tab[n - 1][sum];
// If the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1][sum] = subsetSum(a, n - 1, sum);
else
{
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
return tab[n - 1][sum] = subsetSum(a, n - 1, sum) ||
subsetSum(a, n - 1, sum - a[n - 1]);
}
}
// Driver Code
int main()
{
// Storing the value -1 to the matrix
memset(tab, -1, sizeof(tab));
int n = 5;
int a[] = {1, 5, 3, 7, 4};
int sum = 12;
if (subsetSum(a, n, sum))
{
cout << "YES" << endl;
}
else
cout << "NO" << endl;
/* This Code is Contributed by Ankit Kumar*/
}
// Java program for the above approach
import java.io.*;
class GFG {
// Check if possible subset with
// given sum is possible or not
static int subsetSum(int a[], int n, int sum)
{
// Storing the value -1 to the matrix
int tab[][] = new int[n + 1][sum + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
tab[i][j] = -1;
}
}
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1][sum] != -1)
return tab[n - 1][sum];
// If the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1][sum]
= subsetSum(a, n - 1, sum);
else {
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
if (subsetSum(a, n - 1, sum) != 0
|| subsetSum(a, n - 1, sum - a[n - 1])
!= 0) {
return tab[n - 1][sum] = 1;
}
else
return tab[n - 1][sum] = 0;
}
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
int a[] = { 1, 5, 3, 7, 4 };
int sum = 12;
if (subsetSum(a, n, sum) != 0) {
System.out.println("YES\n");
}
else
System.out.println("NO\n");
}
}
// This code is contributed by rajsanghavi9.
# Python program for the above approach
# Taking the matrix as globally
tab = [[-1 for i in range(2000)] for j in range(2000)]
# Check if possible subset with
# given sum is possible or not
def subsetSum(a, n, sum):
# If the sum is zero it means
# we got our expected sum
if (sum == 0):
return 1
if (n <= 0):
return 0
# If the value is not -1 it means it
# already call the function
# with the same value.
# it will save our from the repetition.
if (tab[n - 1][sum] != -1):
return tab[n - 1][sum]
# If the value of a[n-1] is
# greater than the sum.
# we call for the next value
if (a[n - 1] > sum):
tab[n - 1][sum] = subsetSum(a, n - 1, sum)
return tab[n - 1][sum]
else:
# Here we do two calls because we
# don't know which value is
# full-fill our criteria
# that's why we doing two calls
tab[n - 1][sum] = subsetSum(a, n - 1, sum)
return tab[n - 1][sum] or subsetSum(a, n - 1, sum - a[n - 1])
# Driver Code
if __name__ == '__main__':
n = 5
a = [1, 5, 3, 7, 4]
sum = 12
if (subsetSum(a, n, sum)):
print("YES")
else:
print("NO")
# This code is contributed by shivani.
// C# program for the above approach
using System;
class GFG
{
// Check if possible subset with
// given sum is possible or not
static int subsetSum(int []a, int n, int sum)
{
// Storing the value -1 to the matrix
int [,]tab = new int[n + 1,sum + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
tab[i,j] = -1;
}
}
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1,sum] != -1)
return tab[n - 1,sum];
// If the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1,sum]
= subsetSum(a, n - 1, sum);
else {
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
if (subsetSum(a, n - 1, sum) != 0
|| subsetSum(a, n - 1, sum - a[n - 1])
!= 0) {
return tab[n - 1,sum] = 1;
}
else
return tab[n - 1,sum] = 0;
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 5;
int []a = { 1, 5, 3, 7, 4 };
int sum = 12;
if (subsetSum(a, n, sum) != 0) {
Console.Write("YES\n");
}
else
Console.Write("NO\n");
}
}
// This code is contributed by shivanisinghss2110
<script>
// JavaScript Program for the above approach
// Check if possible subset with
// given sum is possible or not
function subsetSum(a, n, sum) {
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1][sum] != -1)
return tab[n - 1][sum];
// If the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1][sum] = subsetSum(a, n - 1, sum);
else {
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
return tab[n - 1][sum] = subsetSum(a, n - 1, sum) ||
subsetSum(a, n - 1, sum - a[n - 1]);
}
}
// Driver Code
// Storing the value -1 to the matrix
let tab = Array(2000).fill().map(() => Array(2000).fill(-1));
let n = 5;
let a = [1, 5, 3, 7, 4];
let sum = 12;
if (subsetSum(a, n, sum)) {
document.write("YES" + "<br>");
}
else {
document.write("NO" + "<br>");
}
// This code is contributed by Potta Lokesh
</script>
Output
YES
Complexity Analysis:
- Time Complexity: O(sum*n), where sum is the ‘target sum’ and ‘n’ is the size of array.
- Auxiliary Space: O(sum*n) + O(n) -> O(sum*n) = the size of 2-D array is sum*n and O(n)=auxiliary stack space.
Subset Sum Problem
Given a set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum.
Examples:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
Explanation: There is no subset that add up to 30.
Contact Us