Subset Sum Problem | DP-25

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given
set with sum equal to given sum.
Example:

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9

Output: True //There is a subset (4, 5) with sum 9.

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[]
with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems

…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) ||

isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0

Following is naive recursive implementation that simply follows the recursive structure
mentioned above.
div class="responsive-tabs">

C++
// A recursive solution for subset sum problem
#include <stdio.h>

// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;

// If last element is greater than sum, then ignore it

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

/* else, check if sum can be obtained by any of the following

(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1]);
}

// Driver program to test above function

int main()
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(set)/sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}

Java
// A recursive solution for subset sum
// problem
class GFG {

// Returns true if there is a subset

// of set[] with sum equal to given sum
static boolean isSubsetSum(int set[],
int n, int sum)
{
// Base Cases
if (sum == 0)
 return true;
if (n == 0 && sum != 0)
return false;

// If last element is greater than

// sum, then ignore it
if (set[n-1] > sum)
return isSubsetSum(set, n-1, sum);

/* else, check if sum can be obtained

by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1]);
}

/* Driver program to test above function */

public static void main (String args[])
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset"
+ " with given sum");
else
System.out.println("No subset with"
+ " given sum");
}
}

/* This code is contributed by Rajat Mishra */

Python3
# A recursive solution for subset sum
# problem

# Returns true if there is a subset

# of set[] with sun equal to given sum
def isSubsetSum(set,n, sum) :

# Base Cases
if (sum == 0) :
return True
if (n == 0 and sum != 0) :
return False

# If last element is greater than

# sum, then ignore it
if (set[n - 1] > sum) :
return isSubsetSum(set, n - 1, sum);
 # else, check if sum can be obtained
# by any of the following
# (a) including the last element
# (b) excluding the last element
return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1])

# Driver program to test above function

set = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(set)
if (isSubsetSum(set, n, sum) == True) :
print("Found a subset with given sum")
else :
print("No subset with given sum")

# This code is contributed by Nikita Tiwari.

C#
// A recursive solution for subset sum problem
using System;

class GFG
{
// Returns true if there is a subset of set[] with sum
// equal to given sum
static bool isSubsetSum(int []set, int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;

// If last element is greater than sum,

// then ignore it
if (set[n-1] > sum)
return isSubsetSum(set, n-1, sum);

/* else, check if sum can be obtained

by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1]);
}

// Driver program
public static void Main ()
{
int []set = {3, 34, 4, 12, 5, 2};
 int sum = 9;
int n = set.Length;
if (isSubsetSum(set, n, sum) == true)
Console.WriteLine("Found a subset with given sum");
else
Console.WriteLine("No subset with given sum");
}
}

// This code is contributed by Sam007

PHP
<?php
// A recursive solution for subset sum problem

// Returns true if there is a subset of set

// with sun equal to given sum
function isSubsetSum($set, $n, $sum)
{
// Base Cases
if ($sum == 0)
return true;
if ($n == 0 && $sum != 0)
return false;

// If last element is greater

// than sum, then ignore it
if ($set[$n - 1] > $sum)
return isSubsetSum($set, $n - 1, $sum);

/* else, check if sum can be

obtained by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum($set, $n - 1, $sum) ||
isSubsetSum($set, $n - 1,
$sum - $set[$n - 1]);
}

// Driver Code
$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = 6;

if (isSubsetSum($set, $n, $sum) == true)

echo"Found a subset with given sum";
else
echo "No subset with given sum";

// This code is contributed by Anuj_67

?>
Output:
Found a subset with given sum

The above solution may try all subsets of given set in worst case. Therefore time complexity of
the above solution is exponential. The problem is in-fact NP-Complete (There is no known
polynomial time solution for this problem).

We can solve the problem in Pseudo-polynomial time using Dynamic programming. We

create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will
be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false. Finally, we return
subset[sum][n]

C++
// A Dynamic Programming solution for subset sum problem
#include <stdio.h>

// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// The value of subset[i][j] will be true if there is a
// subset of set[0..j-1] with sum equal to i
bool subset[n+1][sum+1];

// If sum is 0, then answer is true

for (int i = 0; i <= n; i++)
subset[i][0] = true;

// If sum is not 0 and set is empty, then answer is false

for (int i = 1; i <= sum; i++)
subset[0][i] = false;

// Fill the subset table in botton up manner

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if(j<set[i-1])
subset[i][j] = subset[i-1][j];
if (j >= set[i-1])
subset[i][j] = subset[i-1][j] ||
subset[i - 1][j-set[i-1]];
}
}

/* // uncomment this code to print table

for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
printf ("%4d", subset[i][j]);
printf(" ");
}*/
 return subset[n][sum];
}

// Driver program to test above function

int main()
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(set)/sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}
// This code is contributed by Arjun Tyagi.

Java
// A Dynamic Programming solution for subset
// sum problem
class GFG {

// Returns true if there is a subset of

// set[] with sun equal to given sum
static boolean isSubsetSum(int set[],
int n, int sum)
{
// The value of subset[i][j] will be
// true if there is a subset of
// set[0..j-1] with sum equal to i
boolean subset[][] =
new boolean[sum+1][n+1];

// If sum is 0, then answer is true

for (int i = 0; i <= n; i++)
subset[0][i] = true;

// If sum is not 0 and set is empty,

// then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;

// Fill the subset table in botton

// up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i][j] = subset[i][j-1];
if (i >= set[j-1])
subset[i][j] = subset[i][j] ||
subset[i - set[j-1]][j-1];
}
 }

/* // uncomment this code to print table

for (int i = 0; i <= sum; i++)
{
for (int j = 0; j <= n; j++)
System.out.println (subset[i][j]);
} */

return subset[sum][n];
}

/* Driver program to test above function */

public static void main (String args[])
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset"
+ " with given sum");
else
System.out.println("No subset with"
+ " given sum");
}
}

/* This code is contributed by Rajat Mishra */

Python3
# A Dynamic Programming solution for subset sum problem
# Returns true if there is a subset of
# set[] with sun equal to given sum

# Returns true if there is a subset of set[]

# with sun equal to given sum
def isSubsetSum(set,n,sum):

# The value of subset[i][j] will be

# true if there is a
# subset of set[0..j-1] with sum equal to i
subset=([[False for i in range(sum+1)]
for i in range(n+1)])

# If sum is 0, then answer is true

for i in range(n+1):
subset[i][0] = True

# If sum is not 0 and set is empty,

# then answer is false
for i in range(1,sum+1):
subset[0][i]=False
 # Fill the subset table in botton up manner
for i in range(1,n+1):
for j in range(1,sum+1):
if j<set[i-1]:
subset[i][j] = subset[i-1][j]
if j>=set[i-1]:
subset[i][j] = (subset[i-1][j] or
subset[i - 1][j-set[i-1]])

# uncomment this code to print table

# for i in range(n+1):
# for j in range(sum+1):
# print (subset[i][j],end=" ")
# print()
return subset[n][sum]

# Driver program to test above function

if __name__=='__main__':
set = [3, 34, 4, 12, 5, 2]
sum = 9
n =len(set)
if (isSubsetSum(set, n, sum) == True):
print("Found a subset with given sum")
else:
print("No subset with given sum")

# This code is contributed by

# sahil shelangia.

C#
// A Dynamic Programming solution for subset sum problem
using System;

class GFG
{
// Returns true if there is a subset
// of set[] with sun equal to given sum
static bool isSubsetSum(int []set, int n, int sum)
{
// The value of subset[i][j] will be true if there
// is a subset of set[0..j-1] with sum equal to i
bool [,]subset = new bool[sum+1,n+1];

// If sum is 0, then answer is true

for (int i = 0; i <= n; i++)
subset[0, i] = true;

// If sum is not 0 and set is empty, then answer is false

for (int i = 1; i <= sum; i++)
subset[i, 0] = false;
 // Fill the subset table in bottom up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i, j] = subset[i, j - 1];
if (i >= set[j - 1])
subset[i, j] = subset[i, j] ||
subset[i - set[j - 1], j - 1];

}
}

return subset[sum,n];
}

// Driver program
public static void Main ()
{
int []set = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.Length;
if (isSubsetSum(set, n, sum) == true)
Console.WriteLine("Found a subset with given sum");
else
Console.WriteLine("No subset with given sum");
}
}
// This code is contributed by Sam007

PHP
<?php
// A Dynamic Programming solution for
// subset sum problem

// Returns true if there is a subset of

// set[] with sun equal to given sum
function isSubsetSum( $set, $n, $sum)
{
// The value of subset[i][j] will
// be true if there is a subset of
// set[0..j-1] with sum equal to i
$subset = array(array());

// If sum is 0, then answer is true

for ( $i = 0; $i <= $n; $i++)
$subset[$i][0] = true;

// If sum is not 0 and set is empty,

// then answer is false
for ( $i = 1; $i <= $sum; $i++)
$subset[0][$i] = false;
 // Fill the subset table in botton
// up manner
for ($i = 1; $i <= $n; $i++)
{
for ($j = 1; $j <= $sum; $j++)
{
if($j < $set[$i-1])
$subset[$i][$j] =
$subset[$i-1][$j];
if ($j >= $set[$i-1])
$subset[$i][$j] =
$subset[$i-1][$j] ||
$subset[$i - 1][$j -
$set[$i-1]];
}
}

/* // uncomment this code to print table

for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
printf ("%4d", subset[i][j]);
printf("n");
}*/

return $subset[$n][$sum];
}

// Driver program to test above function

$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = count($set);

if (isSubsetSum($set, $n, $sum) == true)

echo "Found a subset with given sum";
else
echo "No subset with given sum";

// This code is contributed by anuj_67.

?>
Output:
Found a subset with given sum

Time complexity of the above solution is O(sum*n).

Subset Sum Problem in O(sum) space

Perfect Sum Problem (Print all subsets with given sum)

Please write comments if you find anything incorrect, or you want to share more information
about the topic discussed above