Skip to main content

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 ]
Last updated on by Kalkicode




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