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