C++ program to print all possible subsets of a set














































C++ program to print all possible subsets of a set



Algorithm:

The total number of possible subset a set can have is 2^n, where n is the number of elements in the set.

We can generate all possible subset using binary counter.

                                                        Consider a set 'A' having elements {a, b, c}. So we will generate binary number upto 2^n - 1 (as we will include 0 also).

  • Here n is 3 so we will generate binary number upto 2^3 - 1 (i.e 8-1 = 7)
  • Then we will check which bit in binary counter is set or unset.
  • If ith bit is set , include ith element from the set in current subset.
  • If ith bit is unset , exclude ith element from the set in current subset.
    Binary countersubset formedExplanation
    000{ }as all bits are unset , so exclude all
    001{ a }as only 1st bit is set , we will include only 1st element from the set i.e 'a'
    010{ b }as only 2nd bit is set , we will include only 2nd element from the set i.e 'b'
    011{ a ,b }as 1st and 2nd bits are set , we will include 1st and 2nd element from the set i.e 'a' and 'b'
    100{ c }as only 3rd bit is set , we will include 3rd element from the set i.e 'c'
    101{ a ,c }as 1st and 3rd bits are set , we will include 1st and 3rd element from the set i.e 'a' and 'c'
    110{ b, c }as 2nd and 3rd bits are set , we will include 2nd and 3rd element from the set i.e 'b' and 'c'
    111{ a , b, c }all bits are set , include all elements from the set.
     
  • PROGRAM: 
#include <bits/stdc++.h>
using namespace std;

void Subset(int arr[], int n)
{
    int count = pow(2, n);
    // The outer for loop will run 2^n times to print all subset .
    // Here variable i will act as a binary counter
    for (int i = 0; i < count; i++) {
        // The inner for loop will run n times , 
        // As the maximum number of elements a set can have is n
        // This loop will generate a subset
        for (int j = 0; j < n; j++) {
            // This if condition will check if jth bit in 
            // binary representation of  i  is set or not
            // if the value of (i & (1 << j)) is not 0 , 
            // include arr[j] in the current subset
            // otherwise exclude arr[j]
            if ((i & (1 << j)) != 0)
                cout << arr[j] << " ";
        }
        cout << "\n";
    }
}

int main()
{
    int n;
    
    cout << "Enter size of the set\n";
    cin >> n;

    int arr[n];
    cout << "Enter Elements of the set\n";
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    Subset(arr, n);

    return 0;
}
OUTPUT: Enter size of the set
4
Enter Elements of the set
1 2 3 4

1
2
1 2
3
1 3
2 3
1 2 3
4
1 4
2 4
1 2 4
3 4
1 3 4
2 3 4
1 2 3 4





More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 197 1
C++ program to Sort a Linked List Using Merge Sort 192 1
C++ Program to Implement a Linked List representation of a Binary tree 179 1
C++ Program to Check for balanced parentheses in an expression 130 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 137 1
C++ program to print Indian flag 167 1
C++ program to Convert a multi level linked list to a singly linked list 134 1
C++ program to print right view of a Binary tree using queue 130 1
C++ Program to implement Huffman Coding Compression Algorithm 164 1
C++ Program to Create a Height Balanced Binary Tree 135 1
C++ program to implement Prims algorithm 192 1
C++ Program for BFS Traversal 157 1
C++ Progam to Evaluate a Prefix Expression 153 1
C++ Program to Implement Queue using Linked List 162 1
C++ implementation of Stack using Linked list 160 1
C++ program to find the intersection point of two linked lists 211 1
C++ program to count the inversions in the given array 203 1
C++ program to perform D.N.F sort 218 1
C++ program to print all possible subsets of a String 201 1
C++ program to count the number of ones in a binary representation of a number 219 1
C++ program to print all possible subsets of a set 222 1
C++ program to find the largest word in a String 210 1
C++ Program to print a matrix in Spiral order 217 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 216 1
C limits library 233 1
Program to add two Binary numbers 217 1

Comments