Problem
Suppose, you’ve N elements and you need to find the subsets of these N elements where zero or more of the N elements are included or excluded in a subset.
All of these subsets are called the power set. The powerset of a set S is denoted as P(S) or 2S. If S is a set with the N number of elements, then the number of all the subsets (powerset) of S is 2n. This is also the reason of the notation 2S denoting the power set P(S).

We know that integers are stored as a sequence of bits (0 & 1). Now suppose we need to represent a subset of N elements, we could use an integer 0 <= x < 2N such that, if ith bit of x is 1 it means ith element is included in the subset, and if ith bit of x is 0, the ith element is not included in the subset.

Let N = 3, then the powerset of N: 23 = 8 and 0 <= x < 8:

n2 n1 n0
0  0  0 (0)
0  0  1 (1)
0  1  0 (2)
0  1  1 (3)
1  0  0 (4)
1  0  1 (5)
1  1  0 (6)
1  1  1 (7)
Here, x = 110(6) means a subset with element n0 excluded and elements n1 & n2 included in the subset.
###### Multiplication & Division
Multiplication
Let N = 28, N (binary representation) = (11100)2 (base 2)

N << 1 (shifting bits left by 1) = 56 (111000)2
Shifting bits left by n, means multiplying by 2^n

Division
Similarly, shifting bits right by n, means dividing by 2^n, and we lose n least significant bits (ie. right-most bits)

N = 27, (11011)2
N >> 1 (shifting bits right by 1) = 13 (1101)2
Here we divided by 2 and lost 1 least significant bit.

If we shift by 2:
N = N >> 2
N = 6 (110)2 (divided by 2^2 (4) and lost last 2 significant bits)
###### Including & Excluding the ith element

NOTE: Here elements are counted from the 0th bit

Including ith bit
Let N = 28 (11100) and include the ith bit, i = 1 (2nd element):

To include an element we will use OR (|) operator
i = 1 << 1 = 00010 (2)
N = N | i = 11110 (30)

Excluding ith bit
Let N = 28 (11100) and exclude the ith bit, i = 2 (3rd element)

To exclude an element we will use AND (&) and NOT (~) operator
i = ~(1 << 2) = ~(00100) = (11011)
N = N & i = 11000 (24)
###### Check if the ith element is present
Let N = 28 (11100) and i = 2 (3rd element)

To check if ith element is present, we will use AND (&) operator
i = 1 << 2
x = N & i
if x = 0, ith element is not present, if x = 1 ith element is present
###### Toggle the status of the ith element
Let N = 28 (11100) and i = 2 (3rd element)

To toggle the status of if ith element, we will use XOR (^) operator
i = 1 << 2
N = N^i = (11100)^(00100) = 11000 (24)
###### Practice Problem

Print all the subsets of the given set of N elements such that k elements (k1, k2, k3) are excluded in the subset. You’re given N and an array ki[] of k elements.

• N <= 20
• k <= N
• ki < N
###### Sample Input
N = 3
k = 1
ki = {0}
###### Sample Output
000
010
100
110

Explanation

For N = 3, the subsets are as follows:
n2 n1 n0
0  0  0 (0)
0  0  1 (1)
0  1  0 (2)
0  1  1 (3)
1  0  0 (4)
1  0  1 (5)
1  1  0 (6)
1  1  1 (7)

Now, the subsets with n0 not included or n0 = 0 are the following:
n2 n1 n0
0  0  0 (0)
0  1  0 (2)
1  0  0 (4)
1  1  0 (6)
###### Solution

Approach:
Since n is small, we could use a brute force approach of generating all the subsets (2n) and removing the ones that contains any of the excluded ki (k1, k2, k3..) element.
We’ll be using C++ STL Bitset for representing subsets. Bitset class is like Arrays but stores only boolean values (true/false, 0/1). Also, Bitset is optimized for space allocation: generally, each element occupies only one bit. You could read more about it here.

Code Implementation

//
//  main.cpp
//
//  Created by Himanshu on 18/07/22.
//
#include<iostream>
#include<cmath>
#include <bitset>
#include<vector>
#define N 3
using namespace std;

void findSubsets (int k, int ki[]) {

long subsetCount = (long int)pow(2,(double)N);
for (long i=0; i<subsetCount; i++) {

int pos = 0;  //variable for current bit position (0th - N-1th)

long x = i; //integer to be used for bitmasking (0 <= x < 2^N)

bool flag = false;

bitset<N> subset;
while (x > 0) {
//Checking if the last bit from the right is set or not
if (x&1) {

//Checking if the current bit is the excluded (ki) bit or not
for (int j=0; j<k; j++) {
if (pos == ki[j]) {
flag = true;
}
}

if (flag) {
break;
} else {
//Adding current bit to the subset
subset.set(pos, 1);
}

} else {
//Setting the current bit as 0 if it's unset in x
subset.set(pos, 0);
}

//shifting 1 bit to right, to check the next bit
//and incresing position (pos) of the current bit by 1
x = x >> 1;
pos++;
}

if (!flag) {
cout<<subset<<endl;
}
}

}

int main() {

int k = 1;
int *ki = new int[k]();
ki = 0;

cout<<"Subsets:"<<endl;
findSubsets(k, ki);

return 0;
}


Here’s a working example: Finding Subsets

Similar Practice Problem
Codechef – Mike and Stamps