Skip to main content

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.





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.

New Comment







Nitish Kumar     438 Day ago
thank u!