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
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 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
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 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
{
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 found
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