# 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)
{
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
``````

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