Subset sum using backtracking
In computer science, the subset sum problem is a classic algorithmic problem that seeks to determine if a subset of numbers from a given set adds up to a specific target sum. The problem can be efficiently solved using backtracking, a general algorithmic technique that explores all possible solutions by incrementally building candidates and backtracking when a solution is not feasible.
Problem Statement
Given a set of integers and a target sum, the goal is to find all possible subsets of the set that add up to the target sum. For example, given the set [6, -3, 8, 2, 1, 4, 3] and a target sum of 10, the program should find the following subsets: [8, 2], [6, 4], [-3, 8, 1, 4], [6, -3, 2, 1, 4], [-3, 8, 2, 3], [6, 1, 3], [6, -3, 4, 3], and [2, 1, 4, 3].
Example
Let's take the example of the set [6, -3, 8, 2, 1, 4, 3] with a target sum of 10. We want to find all subsets that add up to 10.
The program starts by initializing an array called "result" to store the elements of each subset. It then uses the "subsetSum" function to recursively find the subsets. The function takes the following parameters: "arr" (the input array), "result" (the array to store the subset), "sum" (the target sum), "size" (the size of the array), "current_sum" (the sum of the current subset), and "location" (the index of the current element).
The "subsetSum" function uses backtracking to explore all possible subsets. It starts by recursively finding subsets without including the current element, then includes the current element and checks if the sum equals the target sum. If a subset with the target sum is found, it prints the subset using the "printSum" function. Finally, it continues to find subsets by recursively including the current element and updating the sum.
The "findSubset" function is responsible for handling the request to find subsets with the target sum. It initializes the "result" array and calls the "subsetSum" function to find the subsets. The function also handles the case when the size of the array is 0 or negative.
Pseudocode Algorithm
function printSum(result[], front, tail):
Print "["
for i from front to tail:
if result[i] is not INT_MAX:
Print result[i]
Print "]"
function subsetSum(arr[], result[], sum, size, current_sum, location):
if location is -1:
return
subsetSum(arr, result, sum, size, current_sum, location - 1)
result[location] = arr[location]
if current_sum + arr[location] equals sum:
printSum(result, location, size)
subsetSum(arr, result, sum, size, current_sum + arr[location], location - 1)
result[location] = INT_MAX
function findSubset(arr[], size, sum):
if size is less than or equal to 0:
return
Create an array called result with size elements
Initialize all elements of result with INT_MAX
Print "Subset Sum of", sum, "is"
Call subsetSum(arr, result, sum, size, 0, size - 1)
arr = [6, -3, 8, 2, 1, 4, 3]
size = length of arr
sum = 10
Call findSubset(arr, size, sum)Code Solution
// 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 ]Explanation
The program finds all possible subsets of the given array that add up to the target sum of 10. It explores different combinations using backtracking and prints the subsets when the sum matches the target sum.
Time Complexity
The time complexity of the subset sum algorithm using backtracking is exponential, specifically O(2^n), where n is the number of elements in the input array. This is because the algorithm explores all possible subsets recursively. As the size of the input array increases, the number of recursive calls and backtracking steps grows exponentially, leading to an exponential time complexity.
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