Subset sum using backtracking
Here given code implementation process.
// C program
// Subset sum using backtracking
#include <stdio.h>
#include <limits.h> //for INT_MAX
// Print result
void printSum(int result[], int front, int tail)
{
printf("[");
for (int i = front; i < tail; ++i)
{
if (result[i] != INT_MAX)
{
printf(" %d ", result[i]);
}
}
printf("]\n");
}
// Finding the subset with given sum in an array
void subsetSum(int arr[], int result[], int sum, int size, int current_sum, int location)
{
if (location == -1)
{
return;
}
// Through by recursion find previous element
subsetSum(arr, result, sum, size, current_sum, location - 1);
// Get element
result[location] = arr[location];
if (current_sum + arr[location] == sum)
{
// When we get sum
printSum(result, location, size);
}
// Through by recursion find previous element
subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1);
result[location] = INT_MAX;
}
// Handles the request to find subset sum
void findSubset(int arr[], int size, int sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
int result[size];
// Set initial value
for (int i = 0; i < size; ++i)
{
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
result[i] = INT_MAX;
}
// Display given sum
printf("Subser Sum of %d is \n", sum);
// Find subset with given sum
subsetSum(arr, result, sum, size, 0, size - 1);
}
int main()
{
// Define array elements
int arr[] = {
6 , -3 , 8 , 2 , 1 , 4 , 3
};
//Get the size
int size = sizeof(arr) / sizeof(arr[0]);
int sum = 10;
findSubset(arr, size, sum);
return 0;
}
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
/*
Java Program for
Subset sum using backtracking
*/
class Subset
{
// Print result
public void printSum(int[] result, int front, int tail)
{
System.out.print("[");
for (int i = front; i < tail; ++i)
{
if (result[i] != Integer.MAX_VALUE)
{
System.out.print(" " + result[i] + " ");
}
}
System.out.print("]\n");
}
// Finding the subset with given sum in an array
public void subsetSum(int[] arr, int[] result, int sum, int size, int current_sum, int location)
{
if (location == -1)
{
return;
}
// Through by recursion find previous element
subsetSum(arr, result, sum, size, current_sum, location - 1);
// Get element
result[location] = arr[location];
if (current_sum + arr[location] == sum)
{
// When we get sum
printSum(result, location, size);
}
// Through by recursion find previous element
subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1);
result[location] = Integer.MAX_VALUE;
}
// Handles the request to find subset sum
public void findSubset(int[] arr, int size, int sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
int[] result = new int[size];
// Set initial value
for (int i = 0; i < size; ++i)
{
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
result[i] = Integer.MAX_VALUE;
}
System.out.print("Subser Sum of " + sum + " is \n");
// Find subset with given sum
subsetSum(arr, result, sum, size, 0, size - 1);
}
public static void main(String[] args)
{
Subset task = new Subset();
// Define array elements
int[] arr = {
6 , -3 , 8 , 2 , 1 , 4 , 3
};
//Get the size
int size = arr.length;
int sum = 10;
task.findSubset(arr, size, sum);
}
}
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
// Include header file
#include <iostream>
#include<limits.h>
using namespace std;
/*
C++ Program for
Subset sum using backtracking
*/
class Subset
{
public:
// Print result
void printSum(int result[], int front, int tail)
{
cout << "[";
for (int i = front; i < tail; ++i)
{
if (result[i] != INT_MAX)
{
cout << " " << result[i] << " ";
}
}
cout << "]\n";
}
// Finding the subset with given sum in an array
void subsetSum(int arr[], int result[], int sum, int size, int current_sum, int location)
{
if (location == -1)
{
return;
}
// Through by recursion find previous element
this->subsetSum(arr, result, sum, size, current_sum, location - 1);
// Get element
result[location] = arr[location];
if (current_sum + arr[location] == sum)
{
// When we get sum
this->printSum(result, location, size);
}
// Through by recursion find previous element
this->subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1);
result[location] = INT_MAX;
}
// Handles the request to find subset sum
void findSubset(int arr[], int size, int sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
int result[size];
// Set initial value
for (int i = 0; i < size; ++i)
{
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
result[i] = INT_MAX;
}
cout << "Subser Sum of " << sum << " is \n";
// Find subset with given sum
this->subsetSum(arr, result, sum, size, 0, size - 1);
}
};
int main()
{
Subset task = Subset();
// Define array elements
int arr[] = {
6 , -3 , 8 , 2 , 1 , 4 , 3
};
//Get the size
int size = sizeof(arr) / sizeof(arr[0]);
int sum = 10;
task.findSubset(arr, size, sum);
return 0;
}
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
// Include namespace system
using System;
/*
C# Program for
Subset sum using backtracking
*/
public class Subset
{
// Print result
public void printSum(int[] result, int front, int tail)
{
Console.Write("[");
for (int i = front; i < tail; ++i)
{
if (result[i] != int.MaxValue)
{
Console.Write(" " + result[i] + " ");
}
}
Console.Write("]\n");
}
// Finding the subset with given sum in an array
public void subsetSum(int[] arr, int[] result, int sum, int size, int current_sum, int location)
{
if (location == -1)
{
return;
}
// Through by recursion find previous element
subsetSum(arr, result, sum, size, current_sum, location - 1);
// Get element
result[location] = arr[location];
if (current_sum + arr[location] == sum)
{
// When we get sum
printSum(result, location, size);
}
// Through by recursion find previous element
subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1);
result[location] = int.MaxValue;
}
// Handles the request to find subset sum
public void findSubset(int[] arr, int size, int sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
int[] result = new int[size];
// Set initial value
for (int i = 0; i < size; ++i)
{
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
result[i] = int.MaxValue;
}
Console.Write("Subser Sum of " + sum + " is \n");
// Find subset with given sum
subsetSum(arr, result, sum, size, 0, size - 1);
}
public static void Main(String[] args)
{
Subset task = new Subset();
// Define array elements
int[] arr = {
6 , -3 , 8 , 2 , 1 , 4 , 3
};
//Get the size
int size = arr.Length;
int sum = 10;
task.findSubset(arr, size, sum);
}
}
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
<?php
/*
Php Program for
Subset sum using backtracking
*/
class Subset
{
// Print result
public function printSum( & $result, $front, $tail)
{
echo "[";
for ($i = $front; $i < $tail; ++$i)
{
if ($result[$i] != PHP_INT_MAX)
{
echo " ". $result[$i] ." ";
}
}
echo "]\n";
}
// Finding the subset with given sum in an array
public function subsetSum( & $arr, & $result, $sum, $size, $current_sum, $location)
{
if ($location == -1)
{
return;
}
// Through by recursion find previous element
$this->subsetSum($arr, $result, $sum, $size, $current_sum, $location - 1);
// Get element
$result[$location] = $arr[$location];
if ($current_sum + $arr[$location] == $sum)
{
// When we get sum
$this->printSum($result, $location, $size);
}
// Through by recursion find previous element
$this->subsetSum($arr, $result, $sum, $size, $current_sum + $arr[$location], $location - 1);
$result[$location] = PHP_INT_MAX;
}
// Handles the request to find subset sum
public function findSubset( & $arr, $size, $sum)
{
if ($size <= 0)
{
return;
}
// Used to collect result
$result = array_fill(0, $size, 0);
// Set initial value
for ($i = 0; $i < $size; ++$i)
{
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
$result[$i] = PHP_INT_MAX;
}
echo "Subser Sum of ". $sum ." is \n";
// Find subset with given sum
$this->subsetSum($arr, $result, $sum, $size, 0, $size - 1);
}
}
function main()
{
$task = new Subset();
// Define array elements
$arr = array(6, -3, 8, 2, 1, 4, 3);
//Get the size
$size = count($arr);
$sum = 10;
$task->findSubset($arr, $size, $sum);
}
main();
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
/*
Node Js Program for
Subset sum using backtracking
*/
class Subset
{
// Print result
printSum(result, front, tail)
{
process.stdout.write("[");
for (var i = front; i < tail; ++i)
{
if (result[i] != Number.MAX_VALUE)
{
process.stdout.write(" " + result[i] + " ");
}
}
process.stdout.write("]\n");
}
// Finding the subset with given sum in an array
subsetSum(arr, result, sum, size, current_sum, location)
{
if (location == -1)
{
return;
}
// Through by recursion find previous element
this.subsetSum(arr, result, sum, size, current_sum, location - 1);
// Get element
result[location] = arr[location];
if (current_sum + arr[location] == sum)
{
// When we get sum
this.printSum(result, location, size);
}
// Through by recursion find previous element
this.subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1);
result[location] = Number.MAX_VALUE;
}
// Handles the request to find subset sum
findSubset(arr, size, sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
var result = Array(size).fill(0);
// Set initial value
for (var i = 0; i < size; ++i)
{
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
result[i] = Number.MAX_VALUE;
}
process.stdout.write("Subser Sum of " + sum + " is \n");
// Find subset with given sum
this.subsetSum(arr, result, sum, size, 0, size - 1);
}
}
function main()
{
var task = new Subset();
// Define array elements
var arr = [6, -3, 8, 2, 1, 4, 3];
//Get the size
var size = arr.length;
var sum = 10;
task.findSubset(arr, size, sum);
}
main();
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
import sys
# Python 3 Program for
# Subset sum using backtracking
class Subset :
# Print result
def printSum(self, result, front, tail) :
print("[", end = "")
i = front
while (i < tail) :
if (result[i] != sys.maxsize) :
print(" ", result[i] ," ", end = "")
i += 1
print("]")
# Finding the subset with given sum in an array
def subsetSum(self, arr, result, sum, size, current_sum, location) :
if (location == -1) :
return
# Through by recursion find previous element
self.subsetSum(arr, result, sum, size, current_sum, location - 1)
# Get element
result[location] = arr[location]
if (current_sum + arr[location] == sum) :
# When we get sum
self.printSum(result, location, size)
# Through by recursion find previous element
self.subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1)
result[location] = sys.maxsize
# Handles the request to find subset sum
def findSubset(self, arr, size, sum) :
if (size <= 0) :
return
# Used to collect result
result = [sys.maxsize] * (size)
print("Subser Sum of ", sum ," is ")
# Find subset with given sum
self.subsetSum(arr, result, sum, size, 0, size - 1)
def main() :
task = Subset()
# Define array elements
arr = [6, -3, 8, 2, 1, 4, 3]
# Get the size
size = len(arr)
sum = 10
task.findSubset(arr, size, sum)
if __name__ == "__main__": main()
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
# Ruby Program for
# Subset sum using backtracking
class Subset
# Print result
def printSum(result, front, tail)
print("[")
i = front
while (i < tail)
if (result[i] != (2 ** (0.size * 8 - 2)))
print(" ", result[i] ," ")
end
i += 1
end
print("]\n")
end
# Finding the subset with given sum in an array
def subsetSum(arr, result, sum, size, current_sum, location)
if (location == -1)
return
end
# Through by recursion find previous element
self.subsetSum(arr, result, sum, size, current_sum, location - 1)
# Get element
result[location] = arr[location]
if (current_sum + arr[location] == sum)
# When we get sum
self.printSum(result, location, size)
end
# Through by recursion find previous element
self.subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1)
result[location] = (2 ** (0.size * 8 - 2))
end
# Handles the request to find subset sum
def findSubset(arr, size, sum)
if (size <= 0)
return
end
# Used to collect result
# Initialize with max value
# Assuming that all elements of are less than the maximum integer
result = Array.new(size) {(2 ** (0.size * 8 - 2))}
print("Subser Sum of ", sum ," is \n")
# Find subset with given sum
self.subsetSum(arr, result, sum, size, 0, size - 1)
end
end
def main()
task = Subset.new()
# Define array elements
arr = [6, -3, 8, 2, 1, 4, 3]
# Get the size
size = arr.length
sum = 10
task.findSubset(arr, size, sum)
end
main()
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
/*
Scala Program for
Subset sum using backtracking
*/
class Subset
{
// Print result
def printSum(result: Array[Int], front: Int, tail: Int): Unit = {
print("[");
var i: Int = front;
while (i < tail)
{
if (result(i) != Int.MaxValue)
{
print(" " + result(i) + " ");
}
i += 1;
}
print("]\n");
}
// Finding the subset with given sum in an array
def subsetSum(arr: Array[Int], result: Array[Int], sum: Int, size: Int, current_sum: Int, location: Int): Unit = {
if (location == -1)
{
return;
}
// Through by recursion find previous element
this.subsetSum(arr, result, sum, size, current_sum, location - 1);
// Get element
result(location) = arr(location);
if (current_sum + arr(location) == sum)
{
// When we get sum
this.printSum(result, location, size);
}
// Through by recursion find previous element
this.subsetSum(arr, result, sum, size, current_sum + arr(location), location - 1);
result(location) = Int.MaxValue;
}
// Handles the request to find subset sum
def findSubset(arr: Array[Int], size: Int, sum: Int): Unit = {
if (size <= 0)
{
return;
}
// Used to collect result
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
var result: Array[Int] = Array.fill[Int](size)(Int.MaxValue);
print("Subser Sum of " + sum + " is \n");
// Find subset with given sum
this.subsetSum(arr, result, sum, size, 0, size - 1);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subset = new Subset();
// Define array elements
var arr: Array[Int] = Array(6, -3, 8, 2, 1, 4, 3);
//Get the size
var size: Int = arr.length;
var sum: Int = 10;
task.findSubset(arr, size, sum);
}
}
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
/*
Swift 4 Program for
Subset sum using backtracking
*/
class Subset
{
// Print result
func printSum(_ result: [Int], _ front: Int, _ tail: Int)
{
print("[", terminator: "");
var i: Int = front;
while (i < tail)
{
if (result[i] != Int.max)
{
print("", result[i] ,"", terminator: "");
}
i += 1;
}
print("]");
}
// Finding the subset with given sum in an array
func subsetSum(_ arr: [Int], _ result: inout[Int], _ sum: Int, _ size: Int, _ current_sum: Int, _ location: Int)
{
if (location == -1)
{
return;
}
// Through by recursion find previous element
self.subsetSum(arr, &result, sum, size, current_sum, location - 1);
// Get element
result[location] = arr[location];
if (current_sum + arr[location] == sum)
{
// When we get sum
self.printSum(result, location, size);
}
// Through by recursion find previous element
self.subsetSum(arr, &result, sum, size, current_sum + arr[location], location - 1);
result[location] = Int.max;
}
// Handles the request to find subset sum
func findSubset(_ arr: [Int], _ size: Int, _ sum: Int)
{
if (size <= 0)
{
return;
}
// Used to collect result
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
var result: [Int] = Array(repeating: Int.max, count: size);
print("Subser Sum of ", sum ," is ");
// Find subset with given sum
self.subsetSum(arr, &result, sum, size, 0, size - 1);
}
}
func main()
{
let task: Subset = Subset();
// Define array elements
let arr: [Int] = [6, -3, 8, 2, 1, 4, 3];
//Get the size
let size: Int = arr.count;
let sum: Int = 10;
task.findSubset(arr, size, sum);
}
main();
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
/*
Kotlin Program for
Subset sum using backtracking
*/
class Subset
{
// Print result
fun printSum(result: Array <Int> , front: Int, tail: Int): Unit
{
print("[");
var i: Int = front;
while (i < tail)
{
if (result[i] != Int.MAX_VALUE)
{
print(" " + result[i] + " ");
}
i += 1;
}
print("]\n");
}
// Finding the subset with given sum in an array
fun subsetSum(arr: Array <Int> , result: Array < Int > , sum: Int, size: Int, current_sum: Int, location: Int): Unit
{
if (location == -1)
{
return;
}
// Through by recursion find previous element
this.subsetSum(arr, result, sum, size, current_sum, location - 1);
// Get element
result[location] = arr[location];
if (current_sum + arr[location] == sum)
{
// When we get sum
this.printSum(result, location, size);
}
// Through by recursion find previous element
this.subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1);
result[location] = Int.MAX_VALUE;
}
// Handles the request to find subset sum
fun findSubset(arr: Array <Int> , size: Int, sum: Int): Unit
{
if (size <= 0)
{
return;
}
// Used to collect result
// Initialize with max value
// Assuming that all elements of are less than the maximum integer
var result: Array <Int> = Array(size)
{
Int.MAX_VALUE
};
print("Subser Sum of " + sum + " is \n");
// Find subset with given sum
this.subsetSum(arr, result, sum, size, 0, size - 1);
}
}
fun main(args: Array <String> ): Unit
{
var task: Subset = Subset();
// Define array elements
var arr: Array <Int> = arrayOf(6, -3, 8, 2, 1, 4, 3);
//Get the size
var size: Int = arr.count();
var sum: Int = 10;
task.findSubset(arr, size, sum);
}
Output
Subser Sum of 10 is
[ 8 2 ]
[ 6 4 ]
[ -3 8 1 4 ]
[ 6 -3 2 1 4 ]
[ -3 8 2 3 ]
[ 6 1 3 ]
[ 6 -3 4 3 ]
[ 2 1 4 3 ]
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