Skip to main content

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 ]
Last updated on by Kalkicode




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