Finding all subsets of a given set
In mathematics, a set is a collection of distinct elements. A subset of a given set is a set that contains some or all of the elements of the original set. In other words, every element in the subset is also an element of the original set.
For example, consider the set A = {1, 2, 3}. Some examples of subsets of A are:
- The empty set, denoted by ∅, which contains no elements.
- {1}, which contains only the element 1.
- {1, 2}, which contains the elements 1 and 2.
- {1, 2, 3}, which is the same as the original set A.
- {2, 3}, which contains the elements 2 and 3.
A key concept to keep in mind when working with subsets is that the order of the elements doesn't matter. For instance, {1, 2} and {2, 1} are considered the same subset of A, even though the order of the elements is different.
It's also worth noting that every set has at least two subsets: the empty set and the set itself. A set with n elements has 2^n possible subsets. For example, the set A = {1, 2, 3} has 2^3 = 8 possible subsets:
- ∅ (the empty set)
- {1}
- {2}
- {3}
- {1, 2}
- {1, 3}
- {2, 3}
- {1, 2, 3} (the set itself)
Subsets are an important concept in many areas of mathematics, including set theory, combinatorics, and topology.
Code Solution
// C program
// Finding all subsets of a given set
// iterative solution
#include <stdio.h>
// Print all possible subsets
void findSubset(char data[], int n)
{
// Number of possible subset
int size = (1 << n);
for (int i = 0; i < size; ++i)
{
printf(" [");
for (int k = 0; k < n && k <= i; ++k)
{
if (((1 << k) & i) > 0)
{
// Include k-th element
printf(" %c ", data[k]);
}
}
printf("]\n");
}
}
int main(int argc, char
const *argv[])
{
// Given set data
char data[] = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get number of elements
int n = sizeof(data) / sizeof(data[0]);
// Test
findSubset(data, n);
return 0;
}
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
// Java program
// Finding all subsets of a given set
// iterative solution
public class Subsets
{
// Print all possible subsets
public void findSubset(char[] data, int n)
{
// Number of possible subset
int size = (1 << n);
for (int i = 0; i < size; ++i)
{
System.out.print(" [");
for (int k = 0; k < n && k <= i; ++k)
{
if (((1 << k) & i) > 0)
{
// Include k-th element
System.out.print(" " + data[k] + " ");
}
}
System.out.print("]\n");
}
}
public static void main(String[] args)
{
Subsets task = new Subsets();
// Given set data
char[] data = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get number of elements
int n = data.length;
// Test
task.findSubset(data, n);
}
}
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
// Include header file
#include <iostream>
using namespace std;
// C++ program
// Finding all subsets of a given set
// iterative solution
class Subsets
{
public:
// Print all possible subsets
void findSubset(char data[], int n)
{
// Number of possible subset
int size = (1 << n);
for (int i = 0; i < size; ++i)
{
cout << " [";
for (int k = 0; k < n && k <= i; ++k)
{
if (((1 << k) &i) > 0)
{
// Include k-th element
cout << " " << data[k] << " ";
}
}
cout << "]\n";
}
}
};
int main()
{
Subsets task = Subsets();
// Given set data
char data[] = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get number of elements
int n = sizeof(data) / sizeof(data[0]);
// Test
task.findSubset(data, n);
return 0;
}
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
// Include namespace system
using System;
// C# program
// Finding all subsets of a given set
// iterative solution
public class Subsets
{
// Print all possible subsets
public void findSubset(char[] data, int n)
{
// Number of possible subset
int size = (1 << n);
for (int i = 0; i < size; ++i)
{
Console.Write(" [");
for (int k = 0; k < n && k <= i; ++k)
{
if (((1 << k) & i) > 0)
{
// Include k-th element
Console.Write(" " + data[k] + " ");
}
}
Console.Write("]\n");
}
}
public static void Main(String[] args)
{
Subsets task = new Subsets();
// Given set data
char[] data = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get number of elements
int n = data.Length;
// Test
task.findSubset(data, n);
}
}
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
<?php
// Php program
// Finding all subsets of a given set
// iterative solution
class Subsets
{
// Print all possible subsets
public function findSubset( & $data, $n)
{
// Number of possible subset
$size = (1 << $n);
for ($i = 0; $i < $size; ++$i)
{
echo " [";
for ($k = 0; $k < $n && $k <= $i; ++$k)
{
if (((1 << $k) & $i) > 0)
{
// Include k-th element
echo " ". $data[$k] ." ";
}
}
echo "]\n";
}
}
}
function main()
{
$task = new Subsets();
// Given set data
$data = array('A', 'B', 'C', 'D', 'E');
// Get number of elements
$n = count($data);
$task->findSubset($data, $n);
}
main();
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
// Node Js program
// Finding all subsets of a given set
// iterative solution
class Subsets
{
// Print all possible subsets
findSubset(data, n)
{
// Number of possible subset
var size = (1 << n);
for (var i = 0; i < size; ++i)
{
process.stdout.write(" [");
for (var k = 0; k < n && k <= i; ++k)
{
if (((1 << k) & i) > 0)
{
// Include k-th element
process.stdout.write(" " + data[k] + " ");
}
}
process.stdout.write("]\n");
}
}
}
function main()
{
var task = new Subsets();
// Given set data
var data = ['A', 'B', 'C', 'D', 'E'];
// Get number of elements
var n = data.length;
// Test
task.findSubset(data, n);
}
main();
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
# Python 3 program
# Finding all subsets of a given set
# iterative solution
class Subsets :
# Print all possible subsets
def findSubset(self, data, n) :
# Number of possible subset
size = (1 << n)
i = 0
k = 0
while (i < size) :
print(" [", end = "")
while (k < n and k <= i) :
if (((1 << k) & i) > 0) :
# Include k-th element
print("", data[k] ,"", end = "")
k += 1
print("]")
i += 1
k = 0
def main() :
task = Subsets()
# Given set data
data = ['A', 'B', 'C', 'D', 'E']
# Get number of elements
n = len(data)
# Test
task.findSubset(data, n)
if __name__ == "__main__": main()
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
# Ruby program
# Finding all subsets of a given set
# iterative solution
class Subsets
# Print all possible subsets
def findSubset(data, n)
# Number of possible subset
size = (1 << n)
i = 0
k = 0
while (i < size)
print(" [")
while (k < n && k <= i)
if (((1 << k) & i) > 0)
# Include k-th element
print(" ", data[k] ," ")
end
k += 1
end
print("]\n")
i += 1
k = 0
end
end
end
def main()
task = Subsets.new()
# Given set data
data = ['A', 'B', 'C', 'D', 'E']
# Get number of elements
n = data.length
# Test
task.findSubset(data, n)
end
main()
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
// Scala program
// Finding all subsets of a given set
// iterative solution
class Subsets
{
// Print all possible subsets
def findSubset(data: Array[Character], n: Int): Unit = {
// Number of possible subset
var size: Int = (1 << n);
var i: Int = 0;
var k: Int = 0;
while (i < size)
{
print(" [");
while (k < n && k <= i)
{
if (((1 << k) & i) > 0)
{
// Include k-th element
print(" " + data(k) + " ");
}
k += 1;
}
print("]\n");
i += 1;
k = 0;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subsets = new Subsets();
// Given set data
var data: Array[Character] = Array('A', 'B', 'C', 'D', 'E');
// Get number of elements
var n: Int = data.length;
// Test
task.findSubset(data, n);
}
}
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
// Swift 4 program
// Finding all subsets of a given set
// iterative solution
class Subsets
{
// Print all possible subsets
func findSubset(_ data: [Character], _ n: Int)
{
// Number of possible subset
let size: Int = (1 << n);
var i: Int = 0;
var k: Int = 0;
while (i < size)
{
print(" [", terminator: "");
while (k < n && k <= i)
{
if (((1 << k) & i) > 0)
{
// Include k-th element
print("", data[k] ,"", terminator: "");
}
k += 1;
}
print("]");
i += 1;
k = 0;
}
}
}
func main()
{
let task: Subsets = Subsets();
// Given set data
let data: [Character] = ["A", "B", "C", "D", "E"];
// Get number of elements
let n: Int = data.count;
// Test
task.findSubset(data, n);
}
main();
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
// Kotlin program
// Finding all subsets of a given set
// iterative solution
class Subsets
{
// Print all possible subsets
fun findSubset(data: Array < Char > , n: Int): Unit
{
// Number of possible subset
var size: Int = (1 shl n);
var i: Int = 0;
var k: Int = 0;
while (i < size)
{
print(" [");
while (k < n && k <= i)
{
if (((1 shl k) and i) > 0)
{
// Include k-th element
print(" " + data[k] + " ");
}
k += 1;
}
print("]\n");
i += 1;
k = 0;
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Subsets = Subsets();
// Given set data
var data: Array < Char > = arrayOf('A', 'B', 'C', 'D', 'E');
// Get number of elements
var n: Int = data.count();
// Test
task.findSubset(data, n);
}
Output
[]
[ A ]
[ B ]
[ A B ]
[ C ]
[ A C ]
[ B C ]
[ A B C ]
[ D ]
[ A D ]
[ B D ]
[ A B D ]
[ C D ]
[ A C D ]
[ B C D ]
[ A B C D ]
[ E ]
[ A E ]
[ B E ]
[ A B E ]
[ C E ]
[ A C E ]
[ B C E ]
[ A B C E ]
[ D E ]
[ A D E ]
[ B D E ]
[ A B D E ]
[ C D E ]
[ A C D E ]
[ B C D E ]
[ A B C D E ]
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