Bit Masking (Subset Generation)

Subset generation using bits (also called bitmasking) is a common and efficient technique to generate all possible subsets (also called the power set) of a given array or list.

---

Concept:

If an array has n elements, there are 2^n possible subsets. Each subset can be represented by a binary number of n bits:

• Each bit in the binary number tells whether to include (1) or exclude (0) the corresponding element.

---

Example:

Given the array:

arr = [1, 2, 3]

There are 2^3 = 8 subsets. We loop from 0 to 7 (inclusive), and for each number, check which bits are set to decide which elements to include.

---

Code (Python):

def generate_subsets(arr):
    n = len(arr)
    subsets = []
    
    for i in range(1 << n):  # from 0 to 2^n - 1
        subset = []
        for j in range(n):
            if i & (1 << j):  # check if j-th bit in i is set
                subset.append(arr[j])
        subsets.append(subset)
    
    return subsets
 
# Example
arr = [1, 2, 3]
all_subsets = generate_subsets(arr)
for subset in all_subsets:
    print(subset)

Code (CPP):

#include <iostream>
#include <vector>
using namespace std;
 
void generateSubsets(vector<int>& arr) {
    int n = arr.size();
    int totalSubsets = 1 << n;  // 2^n subsets
 
    for (int mask = 0; mask < totalSubsets; ++mask) {
        vector<int> subset;
        for (int j = 0; j < n; ++j) {
            if (mask & (1 << j)) {
                subset.push_back(arr[j]);
            }
        }
 
        // Print the subset
        cout << "{ ";
        for (int val : subset) {
            cout << val << " ";
        }
        cout << "}" << endl;
    }
}
 
int main() {
    vector<int> arr = {1, 2, 3};
    generateSubsets(arr);
    return 0;
}

---

Output:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

---

Time Complexity:

• O(n * 2^n) — for each of the 2^n subsets, we loop through up to n elements.