Print all possible subsets of a set in C++
In this tutorial, we will learn how to print all the possible subsets of a set in C++. Now, before moving to the problem which is to print all the possible subsets of a set in C++. Let us understand it with an example, where there were 3 sets {0,1,2} (which means n=3). Hence, the total number of subsets are:
0 1 0 1 2 0 2 1 2 0 1 2
Now, let us understand it more deeply upon the possible subsets. How to get them logically?
As we all know that the total possible subsets in a given set are 2 power n(2^n). It is all based on the counter which is basically of type binary. That is let us understand it for n=3. Where 2 power 3 ( 2^3 ) equals to 8. But, based on our counter(binary) it would be 7 ( 2^n -1 ) where the 000 implies nothing( empty set ).
n=3, sets={1,2,3} BINARY SUBSETS IMPLIES REPRESENTATION 000 {} Nothing(empty set) 001 {1} 1 is set, one set is 1. 010 {2} 2 is set, another set is 2. 011 {1,2} likewise 1,2 is also an set. 100 {3} 3 is also an set. 101 {1,3} 1,3 is also an set. 110 {2,3} 2,3 is also an set. 111 {1,2,3} All the bits are set i.e., 1,2,3.
Lets us construct code based upon the above logic. Its program is :
#include <bits/stdc++.h> using namespace std; void possiblesets(int a[],int num) { // loop running till 2^num - 1 for (int i = 0; i < pow(2,num); i++) { //the jth loop will run till num - 1 times for (int j = 0; j < num; j++) { // the actual logic is checked here and then gets // printed on the console if successfull if ((i & (1 << j)) > 0) cout << a[j] << " "; } cout << "\n"; } } int main() { int num; cout << "Enter the number of elements in the set:\n"; cin >> num; int a[num]; cout << "Enter the elements of the set:\n"; for(int i=0;i<num;i++) cin >> a[i]; possiblesets(a,num); //this function prints all the possible subsets return 0; }
The above program generates the outputs as :
1. Enter the number of elements in the set: 2 Enter the elements of the set: 10 20 10 20 10 20 2. Enter the number of elements in the set: 4 Enter the elements of the set: 0 1 2 3 0 1 0 1 2 0 2 1 2 0 1 2 3 0 3 1 3 0 1 3 2 3 0 2 3 1 2 3 0 1 2 3
Hope you like that guys. Happy learning!
Recommended articles:
C++ program to Count total number of words in a text file
Find substring from text file with C++
Leave a Reply