# Find all subsets of an array c++

In this tutorial, i am going to show you a simple code to find all subsets of an array in c++.

We are going to be using bit manipulation so as to achieve space complexity of O(1). So in case you do not understand bits representation and manipulation, i have linked to 2 previous post that can bring you up to speed.

They algorithm for finding all subsets of an array is simple. We already know that given n set of elements of an array, it is possible to generate 2n subsets. So for instance given an array of say A={A,B,C} we can generate { }, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

So now that we know that we are to generate 2n subsets, we can plan to have an outer for loop that checks that we generate at least 8 subsets. We can design the algorithm such that the outer for loop has an incremental variable say int b (initialized to 0) and incremented each time by 1 until b==2n (b therefore grows from 0 to 1 to 2 to … n-1) before execution can exit the outer loop. When b == 0, subset { } is generated; b == 1, subset {A} is generated; b == 2, subset {B} is generated; b == 3, subset {A,B} is generated; b == 4, subset {C} is generated; b == 5, subset {A,C} is generated; b == 6, subset {B,C} is generated; b == 7, subset {A,B,C} is generated.

See what i mean; b is declared as an int variable meaning that b consist of 32 bits and each bit represent an element in our array – in our particular case, the first 3 bits from the least significant bit represent C,B,A – A being at index 0, B index 1 and C index 2

• So when b == 0, what is the bit representation in terms of C,B,A – 0,0,0
• When b == 1, what is the bit representation in terms of C,B,A – 0,0,1
• When b == 2, what is the bit representation in terms of C,B,A – 0,1,0
• When b == 3, what is the bit representation in terms of C,B,A – 0,1,1
• When b == 4, what is the bit representation in terms of C,B,A – 1,0,0
• When b == 5, what is the bit representation in terms of C,B,A – 1,0,1
• When b == 6, what is the bit representation in terms of C,B,A – 1,1,0
• When b == 7, what is the bit representation in terms of C,B,A – 1,1,1
• So when the bit is 0,0,0, what is the value of the subset printed – { }
• So when the bit is 0,0,1, what is the value of the subset printed – {A}
• So when the bit is 0,1,0, what is the value of the subset printed – {B}
• So when the bit is 0,1,1, what is the value of the subset printed – {A,B}
• When the bit is 1,0,0, what is the value of the subset printed – {C}
• when the bit is 1,0,1, what is the value of the subset printed – {A,C}
• when the bit is 1,1,0, what is the value of the subset printed – {B,C}
• when the bit is 1,1,1, what is the value of the subset printed – {A,B,C}
• See – when 1 is set in a bit position, it means the character at that index in our array is included.
• 0 means that character is not included

If i then have an inner for loop that goes through the bits set in b as b increments from 0 to n-1, i can print all subsets of A = {A,B,C}.

### Code implemented in c++

``````int main(){
vector<char> A = {'A','B','C'};
int n=3;//size of array

for(int b=0;b<(1<<n);b++){//b < 2 raised to the power n
for(int i=0;i<n;i++){//print subsets as b increments
if(b&(1<<i))
cout<<A[i];
}
cout<<" ";
}
}``````

## bfs and dfs program in c++ with output

In this tutorial, i will show you bfs and dfs program in c++ with output. The main difference…

## Coin change problem all combinations in javascript

In this solution, we will be exploring the option of going through all combination to count the number…

## How To Calculate Time Complexity And Space Complexity Of An Algorithm – Big O Notation Examples

How to calculate time complexity and space complexity of an algorithm show developers who are new to the…

## minimum coin change problem with recursion and memoization in javascript

The Problem is to find the minimum number of coins required for constructing a sum. This is a…

## Merge Sort Algorithm With Examples

In this tutorial, i will show you the Merge Sort Algorithm with some examples for quick understanding. I…

## Singly Linked List – Insert a New Node at the beginning of the list each time.

Singly Linked List – Insert each time at beginning of the list. In this tutorial, you will learn…