Find all subsets using backtracking

Here given code implementation process.

/*
   C Program for
   Find all subsets using backtracking
*/
#include <stdio.h>

// Display subset value
void display(int result[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf(" %d", result[i]);
	}
	printf("\n");
}
// Find subset elements
void allSubset(int arr[], int result[], int i, int j, int n)
{
	if (i == n)
	{
		display(result, j);
		return;
	}
	// Get element
	result[j] = arr[i];
	// Through by recursion find next subset
	allSubset(arr, result, i + 1, j + 1, n);
	allSubset(arr, result, i + 1, j, n);
}
// Handles the request to find all subsets
void findSubsets(int arr[], int n)
{
	if (n <= 0)
	{
		return;
	}
	// Used to collect subset element
	int result[n];
	allSubset(arr, result, 0, 0, n);
}
int main()
{
	int arr[] = {
		1 , 2 , 3 , 4 , 5
	};
	// Get the size
	int n = sizeof(arr) / sizeof(arr[0]);
	findSubsets(arr, n);
	return 0;
}

Output

 1 2 3 4 5
 1 2 3 4
 1 2 3 5
 1 2 3
 1 2 4 5
 1 2 4
 1 2 5
 1 2
 1 3 4 5
 1 3 4
 1 3 5
 1 3
 1 4 5
 1 4
 1 5
 1
 2 3 4 5
 2 3 4
 2 3 5
 2 3
 2 4 5
 2 4
 2 5
 2
 3 4 5
 3 4
 3 5
 3
 4 5
 4
 5
/*
   Java Program 
   Find all subsets using backtracking
*/
// Tree Node
class Subset
{
	// Display subset value
	public void display(int[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print("  " + result[i]);
		}
		System.out.print("\n");
	}
	// Find subset elements
	public void allSubset(int[] arr, int[] result, int i, int j, int n)
	{
		if (i == n)
		{
			display(result, j);
			return;
		}
		// Get element
		result[j] = arr[i];
		// Through by recursion find next subset
		allSubset(arr, result, i + 1, j + 1, n);
		allSubset(arr, result, i + 1, j, n);
	}
	// Handles the request to find all subsets
	public void findSubsets(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to collect subset element
		int[] result = new int[n];
		allSubset(arr, result, 0, 0, n);
	}
	public static void main(String[] args)
	{
		Subset task = new Subset();
		int[] arr = 
        {
			1 , 2 , 3 , 4 , 5
		};
		// Get the size
		int n = arr.length;
		task.findSubsets(arr, n);
	}
}

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5
// Include header file
#include <iostream>
using namespace std;
/*
   C++ Program 
   Find all subsets using backtracking
*/
// Tree Node
class Subset
{
	public:
		// Display subset value
		void display(int result[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << "  " << result[i];
			}
			cout << "\n";
		}
	// Find subset elements
	void allSubset(int arr[], int result[], int i, int j, int n)
	{
		if (i == n)
		{
			this->display(result, j);
			return;
		}
		// Get element
		result[j] = arr[i];
		// Through by recursion find next subset
		this->allSubset(arr, result, i + 1, j + 1, n);
		this->allSubset(arr, result, i + 1, j, n);
	}
	// Handles the request to find all subsets
	void findSubsets(int arr[], int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to collect subset element
		int result[n];
		this->allSubset(arr, result, 0, 0, n);
	}
};
int main()
{
	Subset task = Subset();
	int arr[] = {
		1 , 2 , 3 , 4 , 5
	};
	// Get the size
	int n = sizeof(arr) / sizeof(arr[0]);
	task.findSubsets(arr, n);
	return 0;
}

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5
// Include namespace system
using System;
/*
   C# Program 
   Find all subsets using backtracking
*/
// Tree Node
public class Subset
{
	// Display subset value
	public void display(int[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write("  " + result[i]);
		}
		Console.Write("\n");
	}
	// Find subset elements
	public void allSubset(int[] arr, int[] result, int i, int j, int n)
	{
		if (i == n)
		{
			display(result, j);
			return;
		}
		// Get element
		result[j] = arr[i];
		// Through by recursion find next subset
		allSubset(arr, result, i + 1, j + 1, n);
		allSubset(arr, result, i + 1, j, n);
	}
	// Handles the request to find all subsets
	public void findSubsets(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to collect subset element
		int[] result = new int[n];
		allSubset(arr, result, 0, 0, n);
	}
	public static void Main(String[] args)
	{
		Subset task = new Subset();
		int[] arr = {
			1 , 2 , 3 , 4 , 5
		};
		// Get the size
		int n = arr.Length;
		task.findSubsets(arr, n);
	}
}

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5
<?php
/*
   Php Program 
   Find all subsets using backtracking
*/
// Tree Node
class Subset
{
	// Display subset value
	public	function display( & $result, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo "  ". $result[$i];
		}
		echo "\n";
	}
	// Find subset elements
	public	function allSubset( & $arr, & $result, $i, $j, $n)
	{
		if ($i == $n)
		{
			$this->display($result, $j);
			return;
		}
		// Get element
		$result[$j] = $arr[$i];
		// Through by recursion find next subset
		$this->allSubset($arr, $result, $i + 1, $j + 1, $n);
		$this->allSubset($arr, $result, $i + 1, $j, $n);
	}
	// Handles the request to find all subsets
	public	function findSubsets( & $arr, $n)
	{
		if ($n <= 0)
		{
			return;
		}
		// Used to collect subset element
		$result = array_fill(0, $n, 0);
		$this->allSubset($arr, $result, 0, 0, $n);
	}
}

function main()
{
	$task = new Subset();
	$arr = array(1, 2, 3, 4, 5);
	// Get the size
	$n = count($arr);
	$task->findSubsets($arr, $n);
}
main();

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5
/*
   Node Js Program 
   Find all subsets using backtracking
*/
// Tree Node
class Subset
{
	// Display subset value
	display(result, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write("  " + result[i]);
		}
		process.stdout.write("\n");
	}
	// Find subset elements
	allSubset(arr, result, i, j, n)
	{
		if (i == n)
		{
			this.display(result, j);
			return;
		}
		// Get element
		result[j] = arr[i];
		// Through by recursion find next subset
		this.allSubset(arr, result, i + 1, j + 1, n);
		this.allSubset(arr, result, i + 1, j, n);
	}
	// Handles the request to find all subsets
	findSubsets(arr, n)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to collect subset element
		var result = Array(n).fill(0);
		this.allSubset(arr, result, 0, 0, n);
	}
}

function main()
{
	var task = new Subset();
	var arr = [1, 2, 3, 4, 5];
	// Get the size
	var n = arr.length;
	task.findSubsets(arr, n);
}
main();

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5
#    Python 3 Program 
#    Find all subsets using backtracking

#  Tree Node
class Subset :
	#  Display subset value
	def display(self, result, n) :
		i = 0
		while (i < n) :
			print("  ", result[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Find subset elements
	def allSubset(self, arr, result, i, j, n) :
		if (i == n) :
			self.display(result, j)
			return
		
		#  Get element
		result[j] = arr[i]
		#  Through by recursion find next subset
		self.allSubset(arr, result, i + 1, j + 1, n)
		self.allSubset(arr, result, i + 1, j, n)
	
	#  Handles the request to find all subsets
	def findSubsets(self, arr, n) :
		if (n <= 0) :
			return
		
		#  Used to collect subset element
		result = [0] * (n)
		self.allSubset(arr, result, 0, 0, n)
	

def main() :
	task = Subset()
	arr = [1, 2, 3, 4, 5]
	#  Get the size
	n = len(arr)
	task.findSubsets(arr, n)

if __name__ == "__main__": main()

Output

   1   2   3   4   5
   1   2   3   4
   1   2   3   5
   1   2   3
   1   2   4   5
   1   2   4
   1   2   5
   1   2
   1   3   4   5
   1   3   4
   1   3   5
   1   3
   1   4   5
   1   4
   1   5
   1
   2   3   4   5
   2   3   4
   2   3   5
   2   3
   2   4   5
   2   4
   2   5
   2
   3   4   5
   3   4
   3   5
   3
   4   5
   4
   5
#    Ruby Program 
#    Find all subsets using backtracking

#  Tree Node
class Subset 
	#  Display subset value
	def display(result, n) 
		i = 0
		while (i < n) 
			print("  ", result[i])
			i += 1
		end

		print("\n")
	end

	#  Find subset elements
	def allSubset(arr, result, i, j, n) 
		if (i == n) 
			self.display(result, j)
			return
		end

		#  Get element
		result[j] = arr[i]
		#  Through by recursion find next subset
		self.allSubset(arr, result, i + 1, j + 1, n)
		self.allSubset(arr, result, i + 1, j, n)
	end

	#  Handles the request to find all subsets
	def findSubsets(arr, n) 
		if (n <= 0) 
			return
		end

		#  Used to collect subset element
		result = Array.new(n) {0}
		self.allSubset(arr, result, 0, 0, n)
	end

end

def main() 
	task = Subset.new()
	arr = [1, 2, 3, 4, 5]
	#  Get the size
	n = arr.length
	task.findSubsets(arr, n)
end

main()

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5

/*
   Scala Program 
   Find all subsets using backtracking
*/
// Tree Node
class Subset
{
	// Display subset value
	def display(result: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print("  " + result(i));
			i += 1;
		}
		print("\n");
	}
	// Find subset elements
	def allSubset(arr: Array[Int], result: Array[Int], i: Int, j: Int, n: Int): Unit = {
		if (i == n)
		{
			this.display(result, j);
			return;
		}
		// Get element
		result(j) = arr(i);
		// Through by recursion find next subset
		this.allSubset(arr, result, i + 1, j + 1, n);
		this.allSubset(arr, result, i + 1, j, n);
	}
	// Handles the request to find all subsets
	def findSubsets(arr: Array[Int], n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// Used to collect subset element
		var result: Array[Int] = Array.fill[Int](n)(0);
		this.allSubset(arr, result, 0, 0, n);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subset = new Subset();
		var arr: Array[Int] = Array(1, 2, 3, 4, 5);
		// Get the size
		var n: Int = arr.length;
		task.findSubsets(arr, n);
	}
}

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5
/*
   Swift 4 Program 
   Find all subsets using backtracking
*/
// Tree Node
class Subset
{
	// Display subset value
	func display(_ result: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  ", result[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Find subset elements
	func allSubset(_ arr: [Int], _ result: inout[Int], _ i: Int, _ j: Int, _ n: Int)
	{
		if (i == n)
		{
			self.display(result, j);
			return;
		}
		// Get element
		result[j] = arr[i];
		// Through by recursion find next subset
		self.allSubset(arr, &result, i + 1, j + 1, n);
		self.allSubset(arr, &result, i + 1, j, n);
	}
	// Handles the request to find all subsets
	func findSubsets(_ arr: [Int], _ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to collect subset element
		var result: [Int] = Array(repeating: 0, count: n);
		self.allSubset(arr, &result, 0, 0, n);
	}
}
func main()
{
	let task: Subset = Subset();
	let arr: [Int] = [1, 2, 3, 4, 5];
	// Get the size
	let n: Int = arr.count;
	task.findSubsets(arr, n);
}
main();

Output

   1   2   3   4   5
   1   2   3   4
   1   2   3   5
   1   2   3
   1   2   4   5
   1   2   4
   1   2   5
   1   2
   1   3   4   5
   1   3   4
   1   3   5
   1   3
   1   4   5
   1   4
   1   5
   1
   2   3   4   5
   2   3   4
   2   3   5
   2   3
   2   4   5
   2   4
   2   5
   2
   3   4   5
   3   4
   3   5
   3
   4   5
   4
   5
/*
   Kotlin Program 
   Find all subsets using backtracking
*/
// Tree Node
class Subset
{
	// Display subset value
	fun display(result: Array<Int> , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  " + result[i]);
			i += 1;
		}
		print("\n");
	}
	// Find subset elements
	fun allSubset(arr: Array <Int> , result: Array<Int> , i: Int, j: Int, n: Int): Unit
	{
		if (i == n)
		{
			this.display(result, j);
			return;
		}
		// Get element
		result[j] = arr[i];
		// Through by recursion find next subset
		this.allSubset(arr, result, i + 1, j + 1, n);
		this.allSubset(arr, result, i + 1, j, n);
	}
	// Handles the request to find all subsets
	fun findSubsets(arr: Array<Int> , n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// Used to collect subset element
		var result: Array<Int> = Array(n)
		{
			0
		};
		this.allSubset(arr, result, 0, 0, n);
	}
}
fun main(args: Array<String> ): Unit
{
	var task: Subset = Subset();
	var arr: Array<Int> = arrayOf(1, 2, 3, 4, 5);
	// Get the size
	var n: Int = arr.count();
	task.findSubsets(arr, n);
}

Output

  1  2  3  4  5
  1  2  3  4
  1  2  3  5
  1  2  3
  1  2  4  5
  1  2  4
  1  2  5
  1  2
  1  3  4  5
  1  3  4
  1  3  5
  1  3
  1  4  5
  1  4
  1  5
  1
  2  3  4  5
  2  3  4
  2  3  5
  2  3
  2  4  5
  2  4
  2  5
  2
  3  4  5
  3  4
  3  5
  3
  4  5
  4
  5


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







© 2021, kalkicode.com, All rights reserved