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

Your email address will not be published. Required fields are marked *