# Subset sum problem using dynamic programming

Here given code implementation process.

``````/*
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
// Test B
// Sum = 40

}
}``````

#### Output

``````SubSet sum 18 are 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
// Test B
// Sum = 40
return 0;
}``````

#### Output

``````SubSet sum 18 are 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
// Test B
// Sum = 40
}
}``````

#### Output

``````SubSet sum 18 are found
``````package 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
``````<?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
{
}
}
}

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
// Test B
// Sum = 40
}
main();``````

#### Output

``````SubSet sum 18 are 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
// Test B
// Sum = 40
}
main();``````

#### Output

``````SubSet sum 18 are 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 :

def main() :
#  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
#  Test B
#  Sum = 40

if __name__ == "__main__": main()``````

#### Output

``````SubSet sum 18 are 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()
#  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
#  Test B
#  Sum = 40
end

main()``````

#### Output

``````SubSet sum 18 are 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
// Test B
// Sum = 40
}
}``````

#### Output

``````SubSet sum 18 are found
``````import 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
{
}
}
}
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
// Test B
// Sum = 40
}
main();``````

#### Output

``````SubSet sum 18 are 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
// Test B
// Sum = 40
}``````

#### Output

``````SubSet sum 18 are found

## Comment

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.