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.

**Binary representation of int c++**https://firstclicklimited.com/tutorials/index.php/2021/06/13/binary-representation-of-int-c/https://firstclicklimited.com/tutorials/index.php/2021/06/13/binary-representation-of-int-c/- Bits Operations in c++ https://firstclicklimited.com/tutorials/index.php/2021/06/14/bits-operations-in-c/

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 2^{n} 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 2^{n} 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==2^{n} (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<<" ";
}
}
```