Subset sum problem using dynamic programming
The subset sum problem is a classic algorithmic problem in computer science and mathematics. Given a set of positive integers and a target sum, the problem is to determine whether there exists a subset of the given set whose elements sum up to the target sum.
This article presents an implementation of the subset sum problem using dynamic programming in Java. Dynamic programming is a technique that solves complex problems by breaking them down into overlapping subproblems and solving them in a bottom-up manner.
Problem Statement:
We are given a set of positive integers and a target sum. We need to determine whether there exists a subset of the given set whose elements sum up to the target sum.
Pseudocode Algorithm:
1. Create a boolean array "subset" of size (sum + 1) x (n + 1), where sum is the target sum and n is the number of elements in the given set.
2. Initialize the first row of the subset array with "true" values, as the sum 0 can be achieved by selecting an empty subset.
3. Initialize the first column of the subset array with "false" values, except for subset[0][0] which is "true."
4. Iterate through the elements of the given set and for each element:
- Update the subset array as follows:
- If the current element is greater than the current sum value (i.e., data[j - 1] > i), copy the value from the previous element in the same row.
- If the current element is less than or equal to the current sum value, update the value as the logical OR of two conditions:
- The value from the previous element in the same row (subset[i][j - 1]).
- The value at the corresponding position in the subset array for the reduced sum (subset[i - data[j - 1]][j - 1]).
5. The result will be stored in subset[sum][n]. If it is true, the subset sum is found; otherwise, it is not found.
6. Output the result accordingly.
Code Solution
/*
Java program for
Subset sum problem using dynamic programming
*/
public class SubSets
{
public void checkSubsetSum(int data[], int n, int sum)
{
boolean result = true;
if (sum < 0)
{
// Because set include positive values
result = false;
}
else
{
// Assume of, given data contains positive integers
boolean subset[][] = new boolean[sum + 1][n + 1];
// Set value of first row in in subset
for (int i = 0; i <= n && result; ++i)
{
if (i < n && data[i] < 0)
{
// Invalid inputs
// It will work on only positive values
result = false;
}
// When subset sum is zero then result is true
subset[0][i] = true;
}
// Set value of first column in in subset
for (int i = 1; i <= sum && result; ++i)
{
// When subset sum is not zero then result is false
subset[i][0] = false;
}
for (int i = 1; i <= sum && result; ++i)
{
for (int j = 1; j <= n; ++j)
{
// Get a previous element in row
subset[i][j] = subset[i][j - 1];
if (i >= data[j - 1])
{
// Update sub sets value
subset[i][j] = subset[i][j] ||
subset[i - data[j - 1]][j - 1];
}
}
}
if (subset[sum][n] && result)
{
result = true;
}
else
{
result = false;
}
}
if (result)
{
System.out.print("SubSet sum " + sum + " are found\n");
}
else
{
System.out.print("SubSet sum " + sum + " are not found\n");
}
}
public static void main(String[] args)
{
SubSets task = new SubSets();
// Data set which containing positive inputs
int[] data = {
1 , 12 , 9 , 3 , 7 , 4 , 10
};
int n = data.length;
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18);
// Test B
// Sum = 40
task.checkSubsetSum(data, n, 40);
}
}Output
SubSet sum 18 are found
SubSet sum 40 are not found// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Subset sum problem using dynamic programming
*/
class SubSets
{
public: void checkSubsetSum(int data[], int n, int sum)
{
bool result = true;
if (sum < 0)
{
// Because set include positive values
result = false;
}
else
{
// Assume of, given data contains positive integers
bool subset[sum + 1][n + 1];
// Set value of first row in in subset
for (int i = 0; i <= n && result; ++i)
{
if (i < n && data[i] < 0)
{
// Invalid inputs
// It will work on only positive values
result = false;
}
// When subset sum is zero then result is true
subset[0][i] = true;
}
// Set value of first column in in subset
for (int i = 1; i <= sum && result; ++i)
{
// When subset sum is not zero then result is false
subset[i][0] = false;
}
for (int i = 1; i <= sum && result; ++i)
{
for (int j = 1; j <= n; ++j)
{
// Get a previous element in row
subset[i][j] = subset[i][j - 1];
if (i >= data[j - 1])
{
// Update sub sets value
subset[i][j] = subset[i][j] ||
subset[i - data[j - 1]][j - 1];
}
}
}
if (subset[sum][n] && result)
{
result = true;
}
else
{
result = false;
}
}
if (result)
{
cout << "SubSet sum " << sum << " are found\n";
}
else
{
cout << "SubSet sum " << sum << " are not found\n";
}
}
};
int main()
{
SubSets *task = new SubSets();
// Data set which containing positive inputs
int data[] = {
1 , 12 , 9 , 3 , 7 , 4 , 10
};
int n = sizeof(data) / sizeof(data[0]);
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
task->checkSubsetSum(data, n, 18);
// Test B
// Sum = 40
task->checkSubsetSum(data, n, 40);
return 0;
}Output
SubSet sum 18 are found
SubSet sum 40 are not found// Include namespace system
using System;
/*
Csharp program for
Subset sum problem using dynamic programming
*/
public class SubSets
{
public void checkSubsetSum(int[] data, int n, int sum)
{
Boolean result = true;
if (sum < 0)
{
// Because set include positive values
result = false;
}
else
{
// Assume of, given data contains positive integers
Boolean[,] subset = new Boolean[sum + 1,n + 1];
// Set value of first row in in subset
for (int i = 0; i <= n && result; ++i)
{
if (i < n && data[i] < 0)
{
// Invalid inputs
// It will work on only positive values
result = false;
}
// When subset sum is zero then result is true
subset[0,i] = true;
}
// Set value of first column in in subset
for (int i = 1; i <= sum && result; ++i)
{
// When subset sum is not zero then result is false
subset[i,0] = false;
}
for (int i = 1; i <= sum && result; ++i)
{
for (int j = 1; j <= n; ++j)
{
// Get a previous element in row
subset[i,j] = subset[i,j - 1];
if (i >= data[j - 1])
{
// Update sub sets value
subset[i,j] = subset[i,j] ||
subset[i - data[j - 1],j - 1];
}
}
}
if (subset[sum,n] && result)
{
result = true;
}
else
{
result = false;
}
}
if (result)
{
Console.Write("SubSet sum " + sum + " are found\n");
}
else
{
Console.Write("SubSet sum " + sum + " are not found\n");
}
}
public static void Main(String[] args)
{
SubSets task = new SubSets();
// Data set which containing positive inputs
int[] data = {
1 , 12 , 9 , 3 , 7 , 4 , 10
};
int n = data.Length;
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18);
// Test B
// Sum = 40
task.checkSubsetSum(data, n, 40);
}
}Output
SubSet sum 18 are found
SubSet sum 40 are not foundpackage main
import "fmt"
/*
Go program for
Subset sum problem using dynamic programming
*/
func checkSubsetSum(data []int, n int, sum int) {
var result bool = true
if sum < 0 {
// Because set include positive values
result = false
} else {
// Assume of, given data contains positive integers
var subset = make([][]bool,sum+1)
for i := range subset {
subset[i] = make([]bool, n+1)
}
// Set value of first row in in subset
for i := 0 ; i <= n && result ; i++ {
if i < n && data[i] < 0 {
// Invalid inputs
// It will work on only positive values
result = false
}
// When subset sum is zero then result is true
subset[0][i] = true
}
// Set value of first column in in subset
for i := 1 ; i <= sum && result ; i++ {
// When subset sum is not zero then result is false
subset[i][0] = false
}
for i := 1 ; i <= sum && result ; i++ {
for j := 1 ; j <= n ; j++ {
// Get a previous element in row
subset[i][j] = subset[i][j - 1]
if i >= data[j - 1] {
// Update sub sets value
subset[i][j] = subset[i][j] || subset[i - data[j - 1]][j - 1]
}
}
}
if subset[sum][n] && result {
result = true
} else {
result = false
}
}
if result {
fmt.Print("SubSet sum ", sum, " are found\n")
} else {
fmt.Print("SubSet sum ", sum, " are not found\n")
}
}
func main() {
// Data set which containing positive inputs
var data = [] int {1 , 12 , 9 , 3 , 7 , 4 , 10}
var n int = len(data)
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
checkSubsetSum(data, n, 18)
// Test B
// Sum = 40
checkSubsetSum(data, n, 40)
}Output
SubSet sum 18 are found
SubSet sum 40 are not found<?php
/*
Php program for
Subset sum problem using dynamic programming
*/
class SubSets
{
public function checkSubsetSum($data, $n, $sum)
{
$result = true;
if ($sum < 0)
{
// Because set include positive values
$result = false;
}
else
{
// Assume of, given data contains positive integers
$subset = array_fill(0, $sum + 1, array_fill(0, $n + 1, false));
// Set value of first row in in subset
for ($i = 0; $i <= $n && $result; ++$i)
{
if ($i < $n && $data[$i] < 0)
{
// Invalid inputs
// It will work on only positive values
$result = false;
}
// When subset sum is zero then result is true
$subset[0][$i] = true;
}
for ($i = 1; $i <= $sum && $result; ++$i)
{
for ($j = 1; $j <= $n; ++$j)
{
// Get a previous element in row
$subset[$i][$j] = $subset[$i][$j - 1];
if ($i >= $data[$j - 1])
{
// Update sub sets value
$subset[$i][$j] = $subset[$i][$j] ||
$subset[$i - $data[$j - 1]][$j - 1];
}
}
}
if ($subset[$sum][$n] && $result)
{
$result = true;
}
else
{
$result = false;
}
}
if ($result)
{
echo("SubSet sum ".$sum." are found\n");
}
else
{
echo("SubSet sum ".$sum." are not found\n");
}
}
}
function main()
{
$task = new SubSets();
// Data set which containing positive inputs
$data = array(1, 12, 9, 3, 7, 4, 10);
$n = count($data);
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
$task->checkSubsetSum($data, $n, 18);
// Test B
// Sum = 40
$task->checkSubsetSum($data, $n, 40);
}
main();Output
SubSet sum 18 are found
SubSet sum 40 are not found/*
Node JS program for
Subset sum problem using dynamic programming
*/
class SubSets
{
checkSubsetSum(data, n, sum)
{
var result = true;
if (sum < 0)
{
// Because set include positive values
result = false;
}
else
{
// Assume of, given data contains positive integers
var subset = Array(sum + 1).fill(false).map(
() => new Array(n + 1).fill(false));
// Set value of first row in in subset
for (var i = 0; i <= n && result; ++i)
{
if (i < n && data[i] < 0)
{
// Invalid inputs
// It will work on only positive values
result = false;
}
// When subset sum is zero then result is true
subset[0][i] = true;
}
// Set value of first column in in subset
for (var i = 1; i <= sum && result; ++i)
{
// When subset sum is not zero then result is false
subset[i][0] = false;
}
for (var i = 1; i <= sum && result; ++i)
{
for (var j = 1; j <= n; ++j)
{
// Get a previous element in row
subset[i][j] = subset[i][j - 1];
if (i >= data[j - 1])
{
// Update sub sets value
subset[i][j] = subset[i][j] ||
subset[i - data[j - 1]][j - 1];
}
}
}
if (subset[sum][n] && result)
{
result = true;
}
else
{
result = false;
}
}
if (result)
{
process.stdout.write("SubSet sum " + sum + " are found\n");
}
else
{
process.stdout.write("SubSet sum " + sum + " are not found\n");
}
}
}
function main()
{
var task = new SubSets();
// Data set which containing positive inputs
var data = [1, 12, 9, 3, 7, 4, 10];
var n = data.length;
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18);
// Test B
// Sum = 40
task.checkSubsetSum(data, n, 40);
}
main();Output
SubSet sum 18 are found
SubSet sum 40 are not found# Python 3 program for
# Subset sum problem using dynamic programming
class SubSets :
def checkSubsetSum(self, data, n, sum) :
result = True
if (sum < 0) :
# Because set include positive values
result = False
else :
# Assume of, given data contains positive integers
subset = [[False] * (n + 1) for _ in range(sum + 1) ]
i = 0
# Set value of first row in in subset
while (i <= n and result) :
if (i < n and data[i] < 0) :
# Invalid inputs
# It will work on only positive values
result = False
# When subset sum is zero then result is true
subset[0][i] = True
i += 1
i = 1
# Set value of first column in in subset
while (i <= sum and result) :
# When subset sum is not zero then result is false
subset[i][0] = False
i += 1
i = 1
while (i <= sum and result) :
j = 1
while (j <= n) :
# Get a previous element in row
subset[i][j] = subset[i][j - 1]
if (i >= data[j - 1]) :
# Update sub sets value
subset[i][j] = subset[i][j] or subset[i - data[j - 1]][j - 1]
j += 1
i += 1
if (subset[sum][n] and result) :
result = True
else :
result = False
if (result) :
print("SubSet sum", sum ,"are found")
else :
print("SubSet sum", sum ,"are not found")
def main() :
task = SubSets()
# Data set which containing positive inputs
data = [1, 12, 9, 3, 7, 4, 10]
n = len(data)
# Test A
# Sum = 18
# 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18)
# Test B
# Sum = 40
task.checkSubsetSum(data, n, 40)
if __name__ == "__main__": main()Output
SubSet sum 18 are found
SubSet sum 40 are not found# Ruby program for
# Subset sum problem using dynamic programming
class SubSets
def checkSubsetSum(data, n, sum)
result = true
if (sum < 0)
# Because set include positive values
result = false
else
# Assume of, given data contains positive integers
subset = Array.new(sum + 1) {Array.new(n + 1) {false}}
i = 0
# Set value of first row in in subset
while (i <= n && result)
if (i < n && data[i] < 0)
# Invalid inputs
# It will work on only positive values
result = false
end
# When subset sum is zero then result is true
subset[0][i] = true
i += 1
end
i = 1
# Set value of first column in in subset
while (i <= sum && result)
# When subset sum is not zero then result is false
subset[i][0] = false
i += 1
end
i = 1
while (i <= sum && result)
j = 1
while (j <= n)
# Get a previous element in row
subset[i][j] = subset[i][j - 1]
if (i >= data[j - 1])
# Update sub sets value
subset[i][j] = subset[i][j] ||
subset[i - data[j - 1]][j - 1]
end
j += 1
end
i += 1
end
if (subset[sum][n] && result)
result = true
else
result = false
end
end
if (result)
print("SubSet sum ", sum ," are found\n")
else
print("SubSet sum ", sum ," are not found\n")
end
end
end
def main()
task = SubSets.new()
# Data set which containing positive inputs
data = [1, 12, 9, 3, 7, 4, 10]
n = data.length
# Test A
# Sum = 18
# 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18)
# Test B
# Sum = 40
task.checkSubsetSum(data, n, 40)
end
main()Output
SubSet sum 18 are found
SubSet sum 40 are not found
/*
Scala program for
Subset sum problem using dynamic programming
*/
class SubSets()
{
def checkSubsetSum(data: Array[Int], n: Int, sum: Int): Unit = {
var result: Boolean = true;
if (sum < 0)
{
// Because set include positive values
result = false;
}
else
{
// Assume of, given data contains positive integers
var subset: Array[Array[Boolean]] =
Array.fill[Boolean](sum + 1, n + 1)(false);
var i: Int = 0;
// Set value of first row in in subset
while (i <= n && result)
{
if (i < n && data(i) < 0)
{
// Invalid inputs
// It will work on only positive values
result = false;
}
// When subset sum is zero then result is true
subset(0)(i) = true;
i += 1;
}
i = 1;
// Set value of first column in in subset
while (i <= sum && result)
{
// When subset sum is not zero then result is false
subset(i)(0) = false;
i += 1;
}
i = 1;
while (i <= sum && result)
{
var j: Int = 1;
while (j <= n)
{
// Get a previous element in row
subset(i)(j) = subset(i)(j - 1);
if (i >= data(j - 1))
{
// Update sub sets value
subset(i)(j) = subset(i)(j) ||
subset(i - data(j - 1))(j - 1);
}
j += 1;
}
i += 1;
}
if (subset(sum)(n) && result)
{
result = true;
}
else
{
result = false;
}
}
if (result)
{
print("SubSet sum " + sum + " are found\n");
}
else
{
print("SubSet sum " + sum + " are not found\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubSets = new SubSets();
// Data set which containing positive inputs
var data: Array[Int] = Array(1, 12, 9, 3, 7, 4, 10);
var n: Int = data.length;
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18);
// Test B
// Sum = 40
task.checkSubsetSum(data, n, 40);
}
}Output
SubSet sum 18 are found
SubSet sum 40 are not foundimport Foundation;
/*
Swift 4 program for
Subset sum problem using dynamic programming
*/
class SubSets
{
func checkSubsetSum(_ data: [Int], _ n: Int, _ sum: Int)
{
var result: Bool = true;
if (sum < 0)
{
// Because set include positive values
result = false;
}
else
{
// Assume of, given data contains positive integers
var subset: [
[Bool]
] = Array(repeating: Array(repeating: false, count: n + 1),
count: sum + 1);
var i: Int = 0;
// Set value of first row in in subset
while (i <= n && result)
{
if (i < n && data[i] < 0)
{
// Invalid inputs
// It will work on only positive values
result = false;
}
// When subset sum is zero then result is true
subset[0][i] = true;
i += 1;
}
i = 1;
// Set value of first column in in subset
while (i <= sum && result)
{
// When subset sum is not zero then result is false
subset[i][0] = false;
i += 1;
}
i = 1;
while (i <= sum && result)
{
var j: Int = 1;
while (j <= n)
{
// Get a previous element in row
subset[i][j] = subset[i][j - 1];
if (i >= data[j - 1])
{
// Update sub sets value
subset[i][j] = subset[i][j] ||
subset[i - data[j - 1]][j - 1];
}
j += 1;
}
i += 1;
}
if (subset[sum][n] && result)
{
result = true;
}
else
{
result = false;
}
}
if (result)
{
print("SubSet sum", sum ,"are found");
}
else
{
print("SubSet sum", sum ,"are not found");
}
}
}
func main()
{
let task: SubSets = SubSets();
// Data set which containing positive inputs
let data: [Int] = [1, 12, 9, 3, 7, 4, 10];
let n: Int = data.count;
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18);
// Test B
// Sum = 40
task.checkSubsetSum(data, n, 40);
}
main();Output
SubSet sum 18 are found
SubSet sum 40 are not found/*
Kotlin program for
Subset sum problem using dynamic programming
*/
class SubSets
{
fun checkSubsetSum(data: Array < Int > , n: Int, sum: Int): Unit
{
var result: Boolean = true;
if (sum < 0)
{
// Because set include positive values
result = false;
}
else
{
// Assume of, given data contains positive integers
val subset: Array < Array < Boolean >> = Array(sum + 1)
{
Array(n + 1)
{
false
}
};
var i: Int = 0;
// Set value of first row in in subset
while (i <= n && result)
{
if (i < n && data[i] < 0)
{
// Invalid inputs
// It will work on only positive values
result = false;
}
// When subset sum is zero then result is true
subset[0][i] = true;
i += 1;
}
i = 1;
// Set value of first column in in subset
while (i <= sum && result)
{
// When subset sum is not zero then result is false
subset[i][0] = false;
i += 1;
}
i = 1;
while (i <= sum && result)
{
var j: Int = 1;
while (j <= n)
{
// Get a previous element in row
subset[i][j] = subset[i][j - 1];
if (i >= data[j - 1])
{
// Update sub sets value
subset[i][j] = subset[i][j] || subset[i - data[j - 1]][j - 1];
}
j += 1;
}
i += 1;
}
if (subset[sum][n] && result)
{
result = true;
}
else
{
result = false;
}
}
if (result)
{
print("SubSet sum " + sum + " are found\n");
}
else
{
print("SubSet sum " + sum + " are not found\n");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: SubSets = SubSets();
// Data set which containing positive inputs
val data: Array < Int > = arrayOf(1, 12, 9, 3, 7, 4, 10);
val n: Int = data.count();
// Test A
// Sum = 18
// 1 + 7 + 10 = 18
task.checkSubsetSum(data, n, 18);
// Test B
// Sum = 40
task.checkSubsetSum(data, n, 40);
}Output
SubSet sum 18 are found
SubSet sum 40 are not foundExplanation:
The given Java code implements the subset sum problem using dynamic programming. It begins by checking the validity of the input sum value. If the sum is less than 0, it is considered invalid, as the set contains only positive integers.
Next, it creates a 2D boolean array called "subset" to store the results of subproblems. The row represents the sum values from 0 to the target sum, and the column represents the elements of the given set.
The code initializes the first row of the subset array to "true" because an empty subset can achieve a sum of 0. It initializes the first column to "false" except for subset[0][0], which remains "true" since a sum of 0 can be achieved by selecting an empty subset.
Using nested loops, the code iterates through the remaining elements of the set and updates the subset array based on the conditions described in the pseudocode algorithm.
Finally, the code checks the value at subset[sum][n] to determine whether a subset sum with the target value is found. The result is then printed accordingly.
Resultant Output Explanation:
The code includes two test cases:
Test A:
The target sum is 18, and the set contains the following elements: [1, 12, 9, 3, 7, 4, 10].
The program determines that a subset sum of 18 is found, and it outputs "SubSet sum 18 are found". This means that the elements [1, 7, 10] can be selected from the set to achieve the target sum.
Test B:
The target sum is 40, and the set remains the same.
The program determines that a subset sum of 40 is not found, and it outputs "SubSet sum 40 are not found". This means that there is no subset of the given set that sums up to 40.
Time Complexity:
The time complexity of the implemented algorithm is O(sum * n), where sum is the target sum and n is the number of elements in the set. The algorithm uses a nested loop structure to iterate through the subset array, which has dimensions (sum + 1) x (n + 1).
Finally:
In this article, we discussed the subset sum problem and its implementation using dynamic programming. We provided a detailed explanation of the algorithm, including pseudocode and the resultant output explanation. Dynamic programming offers an efficient solution to this problem, making it possible to solve larger instances of the subset sum problem in a reasonable amount of time.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment