Home » C++ programs » C++ Bit manipulation programs

# C++ program to print all possible subset of a set

In this C++ program, we learn how to find and **print the all possible subset of a set**? This page has logic, program and explanation to **print subsets of a set**.

Submitted by **Hritik Raj**, on June 21, 2018

**Problem Statement:**

Print all possible subset of a set

**Example:**

input : {1,2,3,4} output : {} {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}

**Explanation:**

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.

**For example:**

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 i
^{th}bit is set , include i^{th}element from the set in current subset. - If i
^{th}bit is unset , exclude i^{th}element from the set in current subset.

Binary counter | subset formed | Explanation |
---|---|---|

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 allPossibleSubset(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]; allPossibleSubset(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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions