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)
{
int[] arr =
{
1 , 2 , 3 , 4 , 5
};
// Get the size
int n = arr.length;
}
}``````

#### 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()
{
int arr[] = {
1 , 2 , 3 , 4 , 5
};
// Get the size
int n = sizeof(arr) / sizeof(arr[0]);
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)
{
int[] arr = {
1 , 2 , 3 , 4 , 5
};
// Get the size
int n = arr.Length;
}
}``````

#### 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()
{
\$arr = array(1, 2, 3, 4, 5);
// Get the size
\$n = count(\$arr);
}
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 arr = [1, 2, 3, 4, 5];
// Get the size
var n = arr.length;
}
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() :
arr = [1, 2, 3, 4, 5]
#  Get the size
n = len(arr)

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()
arr = [1, 2, 3, 4, 5]
#  Get the size
n = arr.length
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;
}
}``````

#### 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 arr: [Int] = [1, 2, 3, 4, 5];
// Get the size
let n: Int = arr.count;
}
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 arr: Array<Int> = arrayOf(1, 2, 3, 4, 5);
// Get the size
var n: Int = arr.count();
}``````

#### 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.

Categories
Relative Post