Subset Sum Problem using Dynamic Programming
To solve the problem in Pseudo-polynomial time we can use the Dynamic programming approach.
So we will create a 2D array of size (n + 1) * (sum + 1) of type boolean. The state dp[i][j] will be true if there exists a subset of elements from set[0 . . . i] with sum value = ‘j’.
The dynamic programming relation is as follows:
if (A[i-1] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-set[i-1]]
This means that if the current element has a value greater than the ‘current sum value’ we will copy the answer for previous cases and if the current sum value is greater than the ‘ith’ element we will see if any of the previous states have already experienced the sum= j OR any previous states experienced a value ‘j – set[i]’ which will solve our purpose.
Illustration:
See the below illustration for a better understanding:
Consider set[] = {3, 4, 5, 2} and sum = 6.
The table will look like the following where the column number represents the sum and the row number represents the index of set[]:
0
1
2
3
4
5
6
no element (0)
T
F
F
F
F
F
F
0 (3)
T
F
F
T
F
F
F
1 (4)
T
F
F
T
T
F
F
2 (5)
T
F
F
T
T
T
F
3 (2)
T
F
T
T
T
T
T
Below is the implementation of the above approach:
// A Dynamic Programming solution
// for subset sum problem
#include <bits/stdc++.h>
using namespace std;
// Returns true if there is a subset of set[]
// with sum 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 bottom 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]];
}
}
return subset[n][sum];
}
// Driver code
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)
cout << "Found a subset with given sum";
else
cout << "No subset with given sum";
return 0;
}
// This code is contributed by shivanisinghss2110
// A Dynamic Programming solution
// for subset sum problem
#include <stdio.h>
#include <stdbool.h>
// Returns true if there is a subset of set[]
// with sum 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 bottom 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]];
}
}
return subset[n][sum];
}
// Driver code
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.
// A Dynamic Programming solution for subset
// sum problem
import java.io.*;
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)
{
// 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 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 code
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 */
# 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 sum 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 bottom 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]])
return subset[n][sum]
# Driver code
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.
// A Dynamic Programming 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)
{
// 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 code
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
<script>
// A Dynamic Programming solution for subset sum problem
// Returns true if there is a subset of
// set[] with sum 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
let subset = new Array(sum + 1);
for(let i = 0; i < sum + 1; i++)
{
subset[i] = new Array(sum + 1);
for(let j = 0; j < n + 1; j++)
{
subset[i][j] = 0;
}
}
// If sum is 0, then answer is true
for (let i = 0; i <= n; i++)
subset[0][i] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (let i = 1; i <= sum; i++)
subset[i][0] = false;
// Fill the subset table in bottom
// up manner
for (let i = 1; i <= sum; i++) {
for (let 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];
}
let set = [ 3, 34, 4, 12, 5, 2 ];
let sum = 9;
let n = set.length;
if (isSubsetSum(set, n, sum) == true)
document.write("Found a subset" + " with given sum");
else
document.write("No subset with" + " given sum");
// This code is contributed by decode2207.
</script>
<?php
// A Dynamic Programming solution for
// subset sum problem
// Returns true if there is a subset of
// set[] with sum 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 bottom
// 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]];
}
}
return $subset[$n][$sum];
}
// Driver code
$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
Complexity Analysis:
- Time Complexity: O(sum * n), where n is the size of the array.
- Auxiliary Space: O(sum*n), as the size of the 2-D array is sum*n.
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