Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Subset Enumeration
DSA

Subset Enumeration

Learn how bitmasks can efficiently represent and enumerate subsets of a set.

Subset enumeration is one of the cleanest applications of Bit Manipulation.

Every mask is a subset. Decode 101 → {a,c} step by step:

Enumerate Subsets via Bitmask

List every subset of n items by counting from 0 to 2ⁿ−1.

Bit i of the loop counter decides whether items[i] is in the current subset. Counting through all n-bit integers yields every subset exactly once — no recursion, no call stack. O(n·2ⁿ) time, O(1) extra space per mask.

ARRAY VISUALIZER
Steps –
a
0
b
1
c
2
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        n = len(items)
                      
                        2
                        for mask in 0 .. (1 << n) - 1:
                      
                        3
                          subset = []
                      
                        4
                          for i in 0..n-1:
                      
                        5
                            if mask & (1 << i):
                      
                        6
                              subset.add(items[i])
                      
                        7
                          process(subset)

Instead of backtracking, we use a simple idea:

Every subset can be represented by a binary number.

Mental Trigger

n elements → 2ⁿ subsets → binary numbers from 0 to (1 << n) - 1

Each bit tells you:

  • 1 → include element
  • 0 → exclude element

Core Idea

If we have:

arr = [a, b, c]

Then:

000 → {}
001 → {c}
010 → {b}
011 → {b, c}
100 → {a}
...
111 → {a, b, c}

Pattern Table

ConceptMeaning
bit = 1include element
bit = 0skip element
i-th bitarr[i]
range0 → (1 << n) - 1

1. Generic Subset Enumeration Template

Java Code

public List<List<Integer>> generateSubsets(int[] arr) {
    int n = arr.length;
    List<List<Integer>> result = new ArrayList<>();

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {
        List<Integer> subset = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.add(arr[i]);
            }
        }

        result.add(subset);
    }

    return result;
}
def generate_subsets(arr):
    n = len(arr)
    result = []

    total = 1 << n

    for mask in range(total):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(arr[i])

        result.append(subset)

    return result
vector<vector<int>> generateSubsets(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> result;

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {
        vector<int> subset;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.push_back(arr[i]);
            }
        }

        result.push_back(subset);
    }

    return result;
}
function generateSubsets(arr) {
  const n = arr.length;
  const result = [];

  const total = 1 << n;

  for (let mask = 0; mask < total; mask++) {
    const subset = [];

    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        subset.push(arr[i]);
      }
    }

    result.push(subset);
  }

  return result;
}

What Changed from Bit Basics?

We combine two ideas:

1. Loop over all masks

Base idea:

1 << n

Now:

for (int mask = 0; mask < (1 << n); mask++)

because each number is a subset.

2. Check each bit per subset

Base pattern:

(mask & (1 << i)) != 0

meaning:

“Is element i included?”

Subsets = all binary numbers from 0 to 2ⁿ - 1

2. Optimized Bit Iteration (Faster Inner Loop)

Instead of scanning all bits, we iterate only set bits.

Java Code

public List<List<Integer>> generateSubsetsOptimized(int[] arr) {
    int n = arr.length;
    List<List<Integer>> result = new ArrayList<>();

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {
        List<Integer> subset = new ArrayList<>();

        int temp = mask;

        while (temp > 0) {
            int bit = temp & -temp; // lowest set bit
            int idx = Integer.numberOfTrailingZeros(bit);

            subset.add(arr[idx]);

            temp &= (temp - 1); // remove lowest set bit
        }

        result.add(subset);
    }

    return result;
}
def generate_subsets_optimized(arr):
    n = len(arr)
    result = []

    total = 1 << n

    for mask in range(total):
        subset = []

        temp = mask

        while temp > 0:
            bit = temp & -temp  # lowest set bit
            idx = bit.bit_length() - 1

            subset.append(arr[idx])

            temp &= temp - 1  # remove lowest set bit

        result.append(subset)

    return result
vector<vector<int>> generateSubsetsOptimized(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> result;

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {
        vector<int> subset;

        int temp = mask;

        while (temp > 0) {
            int bit = temp & -temp; // lowest set bit
            int idx = __builtin_ctz(bit);

            subset.push_back(arr[idx]);

            temp &= (temp - 1); // remove lowest set bit
        }

        result.push_back(subset);
    }

    return result;
}
function generateSubsetsOptimized(arr) {
  const n = arr.length;
  const result = [];

  const total = 1 << n;

  for (let mask = 0; mask < total; mask++) {
    const subset = [];

    let temp = mask;

    while (temp > 0) {
      const bit = temp & -temp; // lowest set bit
      const idx = Math.log2(bit);

      subset.push(arr[idx]);

      temp &= temp - 1; // remove lowest set bit
    }

    result.push(subset);
  }

  return result;
}

What Changed?

Instead of:

for (int i = 0; i < n; i++)

We do:

while (temp > 0)

because we only process active bits.

Key Trick

temp & -temp

extracts lowest set bit

Only iterate over selected elements instead of full array

3. Fixed-size Subsets (k elements)

Java Code

public List<List<Integer>> kSizedSubsets(int[] arr, int k) {
    int n = arr.length;
    List<List<Integer>> result = new ArrayList<>();

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {

        if (Integer.bitCount(mask) != k) continue;

        List<Integer> subset = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.add(arr[i]);
            }
        }

        result.add(subset);
    }

    return result;
}
def k_sized_subsets(arr, k):
    n = len(arr)
    result = []

    total = 1 << n

    for mask in range(total):
        if bin(mask).count('1') != k:
            continue

        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(arr[i])

        result.append(subset)

    return result
vector<vector<int>> kSizedSubsets(vector<int>& arr, int k) {
    int n = arr.size();
    vector<vector<int>> result;

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {
        if (__builtin_popcount(mask) != k) continue;

        vector<int> subset;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.push_back(arr[i]);
            }
        }

        result.push_back(subset);
    }

    return result;
}
function kSizedSubsets(arr, k) {
  const n = arr.length;
  const result = [];

  const total = 1 << n;

  for (let mask = 0; mask < total; mask++) {
    if (mask.toString(2).replaceAll('0', '').length !== k) continue;

    const subset = [];

    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        subset.push(arr[i]);
      }
    }

    result.push(subset);
  }

  return result;
}

What Changed?

Added constraint:

Integer.bitCount(mask) != k

because we only want subsets of size k.

Bit count = subset size

4. Subsets of String Characters

Java Code

public List<String> stringSubsets(String s) {
    int n = s.length();
    List<String> result = new ArrayList<>();

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sb.append(s.charAt(i));
            }
        }

        result.add(sb.toString());
    }

    return result;
}
def string_subsets(s):
    n = len(s)
    result = []

    total = 1 << n

    for mask in range(total):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(s[i])

        result.append(''.join(subset))

    return result
vector<string> stringSubsets(string s) {
    int n = s.size();
    vector<string> result;

    int total = 1 << n;

    for (int mask = 0; mask < total; mask++) {
        string sub;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sub += s[i];
            }
        }

        result.push_back(sub);
    }

    return result;
}
function stringSubsets(s) {
  const n = s.length;
  const result = [];

  const total = 1 << n;

  for (let mask = 0; mask < total; mask++) {
    let sub = '';

    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        sub += s[i];
      }
    }

    result.push(sub);
  }

  return result;
}

Subset generation works for arrays, strings, and even grids

Pattern Evolution

Bit Basics
   ↓
Mask = 1 << i
   ↓
Check bits in number
   ↓
Generate all masks (0 → 2ⁿ - 1)
   ↓
Build subsets using active bits

Common Mistakes

Using i < n inside wrong loop

for (int mask = 0; mask < n; mask++) // wrong

Correct:

for (int mask = 0; mask < (1 << n); mask++)

Forgetting bit check

subset.add(arr[i]); // wrong (adds everything)

Wrong condition

if ((mask & (1 << i)) == 1) // wrong

Correct:

!= 0

Recognition Cheat Sheet

If you see…Think…
“all subsets”0 → 2ⁿ - 1
“include/exclude choices”bitmask
“fixed k elements”bitCount
“string combinations”bit iteration

My Private Notes

Notes are auto-saved locally to this device.