Posted on by Kalkicode
Code Backtracking

Find all subsets using backtracking

In this article, we will explore how to find all subsets of a given set using the backtracking technique. Backtracking is an algorithmic approach that involves exploring all possible solutions by incrementally building a solution and undoing some of the choices made if they lead to a dead end. The problem we will address is finding all subsets of a given set.

Problem Statement

Given a set of elements, we want to find all possible subsets of that set. For example, given the set {1, 2, 3}, the subsets are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}.

Algorithm

We can solve this problem using a recursive backtracking algorithm. The main idea is to generate all subsets by including or excluding each element in the set. Here's the algorithm:

  1. Define a function called display(result, n) that takes an array result and its size n as input. This function will be used to display the subsets.

  2. Define a recursive function called allSubset(arr, result, i, j, n) that takes the input array arr, the temporary result array result, the current index i, the result array index j, and the size of the set n.

  3. Check if i is equal to n. If true, it means we have reached the end of the set. In this case, call the display() function to print the subset stored in the result array and return.

  4. Assign the value of arr[i] to result[j], indicating that we are including the current element in the subset.

  5. Make two recursive calls to allSubset() with different parameters:

    • Increment i and j by 1 and call allSubset(arr, result, i + 1, j + 1, n). This represents including the current element in the subset.
    • Only increment i by 1 and call allSubset(arr, result, i + 1, j, n). This represents excluding the current element from the subset.
  6. Define a function called findSubsets(arr, n) that takes the input array arr and the size of the set n as parameters.

  7. Check if n is less than or equal to 0. If true, return as there are no elements in the set.

  8. Create an array called result of size n.

  9. Call the allSubset() function with initial values of arr, result, 0, 0, and n to start finding all subsets.

  10. In the main function, initialize the input array arr with the desired set elements.

  11. Calculate the size of the array using sizeof(arr) / sizeof(arr[0]).

  12. Call the findSubsets() function with arr and n to find and display all subsets.

Let's go through the algorithm step by step:

  1. The display(result, n) function is responsible for printing the subsets.
  2. The allSubset(arr, result, i, j, n) function is a recursive function that generates all subsets of the set arr. It starts at index i and fills the result array at index j.
  3. If i reaches the size of the set, we have generated a subset, so we call the display() function to print the subset and return.
  4. Otherwise, we have two recursive calls: one including the current element and one excluding it. We increment both i and j for the recursive calls.
  5. The findSubsets(arr, n) function initializes the result array and calls allSubset() to find all subsets.

Example

Let's take an example to understand the algorithm better. Consider the set {1, 2, 3, 4, 5}. The output will be the following subsets:

    
{}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}, {1, 2, 3, 4}, {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},
{2, 3, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 3}, {2, 4, 5}, {2, 4}, {2, 5}, {3, 4, 5}, {3, 4}, {3, 5},
{4, 5}, {4}, {5}

Code Solution

/*
   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

Time Complexity

The time complexity of this algorithm is O(2^n), where n is the size of the set. This is because for each element in the set, we have two choices: include it or exclude it. Since there are n elements in the set, we have a total of 2^n subsets.

Finally

In this article, we discussed how to find all subsets of a given set using the backtracking technique. We explored the problem statement, provided a step-by-step explanation of the algorithm, and discussed an example and the time complexity of the code. Backtracking is a powerful technique for solving problems that involve exhaustive search, and it can be applied to a wide range of problems.

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