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.

• 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ⁿ 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ⁿ 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ⁿ (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<<" ";
    }
}

Output