Subsets Using Bitmask

🎯

Subsets Using Bitmask

mediumBIT_MANIPULATIONAmazonGoogleFacebook

Imagine you have a set of unique items and want to explore every possible combination you can make from them, like trying all toppings on a pizza to find your favorite.

💡 This problem is about generating all subsets (the power set) of a given set. Beginners often struggle because the number of subsets grows exponentially, and they may not see how bit manipulation can elegantly represent and generate all subsets efficiently.

📋

Problem Statement

Given an array of unique integers nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Input: An array of unique integers nums. Output: A list of lists, where each list is a subset of nums.

1 ≤ n ≤ 20Elements in nums are unique integersEach element fits in 32-bit integer

💡

Example

Input"[1,2,3]"

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

There are 2^3=8 subsets. Each subset corresponds to a bitmask from 0 to 7, where bit i indicates inclusion of nums[i].

• Empty input array → output [[]]
• Single element array → output [[], [element]]
• Array with maximum allowed size (n=20) → ensure performance
• Array with negative and positive integers → subsets include all combinations

⚠️

Common Mistakes

Not copying the current subset before adding to results

All subsets in results end up being the same final list due to reference sharing

✅ Add a copy of the current subset (e.g., path[:], new ArrayList<>(path)) when appending to results

Using bitmask range incorrectly (e.g., up to 2^n instead of 2^n - 1)

Index out of range or extra invalid subsets generated

✅ Use range from 0 to (1 << n) - 1 inclusive

Not backtracking properly by forgetting to remove last element after recursion

Subsets accumulate extra elements, producing incorrect results

✅ Always remove the last added element after recursive call returns

Assuming input can be very large (n > 20) and trying to generate all subsets

Code runs too long or crashes due to exponential time and memory

✅ Clarify constraints and explain exponential complexity; avoid generating all subsets for large n

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem deeply by exploring all subset possibilities explicitly, even if it's not the most efficient.

Intuition

We recursively decide for each element whether to include it in the current subset or not, exploring all 2^n combinations.

Algorithm

1. Start with an empty subset and index 0.
2. At each index, recursively explore two paths: include the current element or exclude it.
3. When index reaches the end, add the current subset to the results.
4. Return all collected subsets.

💡 The recursion tree doubles at each step, which can be hard to visualize initially, but it systematically covers all subsets.

</>

Code

def subsets(nums):
    res = []
    def backtrack(i, path):
        if i == len(nums):
            res.append(path[:])
            return
        # Exclude nums[i]
        backtrack(i + 1, path)
        # Include nums[i]
        path.append(nums[i])
        backtrack(i + 1, path)
        path.pop()
    backtrack(0, [])
    return res

# Driver code
if __name__ == '__main__':
    print(subsets([1,2,3]))

Line Notes

def subsets(nums):Defines the main function to generate subsets

def backtrack(i, path):Helper recursive function with current index and current subset

if i == len(nums):Base case: all elements considered, add current subset copy to results

backtrack(i + 1, path)Explore path excluding current element

path.append(nums[i])Include current element before next recursion

path.pop()Backtrack to remove last element and explore other paths

backtrack(0, [])Start recursion from index 0 with empty subset

import java.util.*;
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int[] nums, int i, List<Integer> path, List<List<Integer>> res) {
        if (i == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // Exclude nums[i]
        backtrack(nums, i + 1, path, res);
        // Include nums[i]
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsets(new int[]{1,2,3}));
    }
}

Line Notes

public List<List<Integer>> subsets(int[] nums)Main method to generate subsets

private void backtrack(int[] nums, int i, List<Integer> path, List<List<Integer>> res)Recursive helper with current index and subset

if (i == nums.length)Base case: all elements processed, add copy of path

backtrack(nums, i + 1, path, res);Explore excluding current element

path.add(nums[i]);Include current element before recursion

path.remove(path.size() - 1);Backtrack by removing last element

public static void main(String[] args)Driver code to test the solution

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void backtrack(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res) {
        if (i == nums.size()) {
            res.push_back(path);
            return;
        }
        // Exclude nums[i]
        backtrack(nums, i + 1, path, res);
        // Include nums[i]
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.pop_back();
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return res;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,2,3};
    vector<vector<int>> result = sol.subsets(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

void backtrack(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res)Recursive helper with current index and current subset

if (i == nums.size())Base case: all elements considered, add current subset

backtrack(nums, i + 1, path, res);Explore excluding current element

path.push_back(nums[i]);Include current element before recursion

path.pop_back();Backtrack by removing last element

vector<vector<int>> subsets(vector<int>& nums)Main function to initiate recursion

int main()Driver code to test the solution

function subsets(nums) {
    const res = [];
    function backtrack(i, path) {
        if (i === nums.length) {
            res.push([...path]);
            return;
        }
        // Exclude nums[i]
        backtrack(i + 1, path);
        // Include nums[i]
        path.push(nums[i]);
        backtrack(i + 1, path);
        path.pop();
    }
    backtrack(0, []);
    return res;
}

// Driver code
console.log(subsets([1,2,3]));

Line Notes

function subsets(nums)Main function to generate all subsets

function backtrack(i, path)Recursive helper with current index and current subset

if (i === nums.length)Base case: all elements processed, add copy of path

backtrack(i + 1, path);Explore excluding current element

path.push(nums[i]);Include current element before recursion

path.pop();Backtrack by removing last element

backtrack(0, []);Start recursion from index 0 with empty subset

⏱

Complexity

TimeO(n * 2^n)

SpaceO(n * 2^n)

There are 2^n subsets, and each subset can take up to O(n) space to store. The recursion tree has 2^n leaves.

💡 For n=20, 2^20 is about 1 million, so this approach is feasible but can be slow for larger n.

Interview Verdict: Accepted

Though exponential, this approach is straightforward and accepted for n up to around 20, which is typical for subset generation problems.

🧠

Bitmask Enumeration

💡 This approach uses bit manipulation to generate subsets iteratively, which is often faster and more intuitive once you understand binary representation.

Intuition

Each subset corresponds to a bitmask from 0 to 2^n - 1, where the i-th bit indicates whether nums[i] is included.

Algorithm

1. Calculate total subsets as 2^n.
2. For each number from 0 to 2^n - 1, interpret its bits as subset inclusion flags.
3. For each bit set in the number, include the corresponding element in the subset.
4. Add the constructed subset to the result list.

💡 This approach avoids recursion and uses simple loops, making it easier to implement and understand once you grasp bit operations.

</>

Code

def subsets(nums):
    n = len(nums)
    res = []
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        res.append(subset)
    return res

# Driver code
if __name__ == '__main__':
    print(subsets([1,2,3]))

Line Notes

n = len(nums)Store length of input for bitmask size

for mask in range(1 << n):Iterate over all bitmasks from 0 to 2^n - 1

if mask & (1 << i):Check if i-th bit is set in mask to include nums[i]

subset.append(nums[i])Add element to current subset if bit is set

res.append(subset)Add constructed subset to results

import java.util.*;
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            res.add(subset);
        }
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsets(new int[]{1,2,3}));
    }
}

Line Notes

int n = nums.length;Store length of input array

for (int mask = 0; mask < (1 << n); mask++)Iterate over all bitmasks representing subsets

if ((mask & (1 << i)) != 0)Check if i-th bit is set in mask

subset.add(nums[i]);Include nums[i] in current subset

res.add(subset);Add current subset to results

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        for (int mask = 0; mask < (1 << n); mask++) {
            vector<int> subset;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subset.push_back(nums[i]);
                }
            }
            res.push_back(subset);
        }
        return res;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,2,3};
    vector<vector<int>> result = sol.subsets(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

int n = nums.size();Store input size for bitmask length

for (int mask = 0; mask < (1 << n); mask++)Loop over all bitmasks from 0 to 2^n - 1

if (mask & (1 << i))Check if bit i is set in mask

subset.push_back(nums[i]);Include nums[i] in current subset

res.push_back(subset);Add subset to results vector

function subsets(nums) {
    const n = nums.length;
    const res = [];
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) !== 0) {
                subset.push(nums[i]);
            }
        }
        res.push(subset);
    }
    return res;
}

// Driver code
console.log(subsets([1,2,3]));

Line Notes

const n = nums.length;Store length of input array

for (let mask = 0; mask < (1 << n); mask++)Iterate over all bitmasks representing subsets

if ((mask & (1 << i)) !== 0)Check if bit i is set in mask

subset.push(nums[i]);Include nums[i] in current subset

res.push(subset);Add current subset to results

⏱

Complexity

TimeO(n * 2^n)

SpaceO(n * 2^n)

We generate 2^n subsets, each subset can have up to n elements, so total time and space is O(n * 2^n).

💡 This approach is often faster in practice than recursion due to iteration and bit operations.

Interview Verdict: Accepted

This is the preferred approach in interviews for subset generation due to clarity and efficiency.

🧠

Backtracking with Early Pruning (Sorting + Recursive)

💡 This approach is useful when input may contain duplicates (not in this problem), but here it shows how sorting and pruning can optimize subset generation.

Intuition

Sort the array to handle duplicates and recursively build subsets, skipping duplicates to avoid repeated subsets.

Algorithm

1. Sort the input array (not strictly needed here as input is unique).
2. Recursively build subsets by choosing to include or skip elements.
3. Skip elements that are the same as previous to avoid duplicates.
4. Add each constructed subset to results.

💡 Though pruning is not needed here, this approach generalizes well and shows control over recursion paths.

</>

Code

def subsets(nums):
    nums.sort()
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            # No duplicates check needed here since unique input
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

# Driver code
if __name__ == '__main__':
    print(subsets([1,2,3]))

Line Notes

nums.sort()Sort input to prepare for pruning (not needed here but good habit)

res = []Initialize result list

def backtrack(start, path):Recursive helper with start index and current subset

res.append(path[:])Add current subset to results at each recursion level

for i in range(start, len(nums))Iterate over remaining elements to include

path.append(nums[i])Include current element

backtrack(i + 1, path)Recurse with next index

path.pop()Backtrack by removing last element

import java.util.*;
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            // No duplicates check needed here
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsets(new int[]{1,2,3}));
    }
}

Line Notes

Arrays.sort(nums);Sort input array for pruning (not needed here but good practice)

List<List<Integer>> res = new ArrayList<>();Initialize result list

res.add(new ArrayList<>(path));Add current subset copy to results

for (int i = start; i < nums.length; i++)Iterate over remaining elements

path.add(nums[i]);Include current element

backtrack(nums, i + 1, path, res);Recurse with next index

path.remove(path.size() - 1);Backtrack by removing last element

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path);
        for (int i = start; i < nums.size(); i++) {
            // No duplicates check needed here
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return res;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,2,3};
    vector<vector<int>> result = sol.subsets(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort input array for pruning (not needed here but good practice)

res.push_back(path);Add current subset to results

for (int i = start; i < nums.size(); i++)Iterate over remaining elements

path.push_back(nums[i]);Include current element

backtrack(nums, i + 1, path, res);Recurse with next index

path.pop_back();Backtrack by removing last element

function subsets(nums) {
    nums.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path) {
        res.push([...path]);
        for (let i = start; i < nums.length; i++) {
            // No duplicates check needed here
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    backtrack(0, []);
    return res;
}

// Driver code
console.log(subsets([1,2,3]));

Line Notes

nums.sort((a,b) => a - b);Sort input array for pruning (not needed here but good practice)

res.push([...path]);Add current subset copy to results

for (let i = start; i < nums.length; i++)Iterate over remaining elements

path.push(nums[i]);Include current element

backtrack(i + 1, path);Recurse with next index

path.pop();Backtrack by removing last element

⏱

Complexity

TimeO(n * 2^n)

SpaceO(n * 2^n)

We generate all subsets recursively; sorting adds O(n log n) but is negligible compared to 2^n growth.

💡 This approach is more general and useful when duplicates exist, but here it performs similarly to brute force.

Interview Verdict: Accepted

Though not necessary here, this approach shows good habits and prepares you for similar problems with duplicates.

📊

All Approaches - One-Glance Tradeoffs

💡 Bitmask enumeration is the best balance of clarity and efficiency for this problem and should be your go-to in interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursion)	O(n * 2^n)	O(n * 2^n)	Yes (deep recursion for large n)	Yes	Good to explain conceptually, but avoid coding if bitmask is allowed
2. Bitmask Enumeration	O(n * 2^n)	O(n * 2^n)	No	Yes	Preferred approach to code in interviews
3. Backtracking with Pruning	O(n * 2^n)	O(n * 2^n)	Yes	Yes	Mention if duplicates exist; otherwise similar to brute force

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints, confirm input uniqueness.Step 2: Present the brute force recursive approach to show understanding of subset generation.Step 3: Introduce bitmask enumeration as an efficient iterative alternative.Step 4: Optionally mention backtracking with pruning for duplicates (even if not needed here).Step 5: Code the chosen approach carefully, test on examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of subset generation, bit manipulation, recursion, and ability to optimize and handle edge cases.

Common Follow-ups

• How to handle duplicates in input? → Use sorting + skip duplicates during recursion.
• Can you generate subsets in lexicographical order? → Sort input and carefully order recursion or bitmask enumeration.

💡 These follow-ups test your ability to adapt the base solution to more complex scenarios and ordering requirements.

🔍

Pattern Recognition

When to Use

1) Asked to generate all subsets or power set; 2) Input size small to medium (n ≤ 20); 3) Need to enumerate all combinations; 4) Bit manipulation or recursion is allowed.

Signature Phrases

generate all subsetspower setall combinations

NOT This Pattern When

Problems asking for subsets with sum constraints or optimization often require DP or backtracking with pruning.

Similar Problems

Subsets II - handles duplicates by pruningCombination Sum - subset sums with targetPower Set - classic subset generation

Practice

1. Consider the following code snippet implementing the trie-based maximum XOR finder. Given the input array [2, 8], what is the return value of findMaximumXOR([2, 8])?

easy

A. 2

B. 8

C. 10

D. 0

Solution

1. Step 1: Insert numbers 2 and 8 into trie

   2 in binary: 000...0010, 8 in binary: 000...1000. Trie stores bits for both numbers.

2. Step 2: For each number, find max XOR partner

   For 2, try to find bits opposite to 2's bits in trie. At bit 3 (8's highest set bit), toggled bit exists, so max_xor |= 8. At bit 1, toggled bit exists, max_xor |= 2. Total max_xor = 10.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   2 XOR 8 = 10, which is maximum XOR [OK]

Hint: XOR of 2 and 8 is 10, max XOR found [OK]

Common Mistakes:

• Confusing max_xor with input number
• Off-by-one bit indexing
• Returning XOR with self

2. Identify the bug in the following code snippet for bitwise AND of numbers range:

medium

A. The bit-clearing operation 'right = right & (right - 1)' is incorrect.

B. There is no bug; the code works correctly.

C. The function should return 'left' instead of 'right'.

D. The loop condition should be 'right > left' instead of 'right != left'.

Solution

1. Step 1: Analyze loop condition

   The loop runs while right != left, which fails if right < left, causing infinite loop or incorrect behavior.

2. Step 2: Correct condition

   Changing condition to 'right > left' ensures loop terminates when right reaches or goes below left.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must prevent infinite loops and handle equality correctly [OK]

Hint: Loop condition must be 'right > left' to terminate properly [OK]

Common Mistakes:

• Using '!=' instead of '>' causes infinite loops
• Misunderstanding bit-clearing operation
• Returning wrong variable

3. What is the time complexity of the trie-based maximum XOR algorithm for an input array of size n, where each number fits in 32 bits?

medium

A. O(n^2)

B. O(n * log M), where M is the max number value

C. O(n * 32^2)

D. O(n * 32)

Solution

1. Step 1: Identify operations per number

   Each number is inserted into the trie by processing 32 bits, so insertion is O(32) per number.

2. Step 2: Find max XOR per number

   For each number, traversing trie to find max XOR also takes O(32) steps.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity is O(n * 32) = O(n), since 32 is constant [OK]

Hint: 32 bits fixed, so linear in n [OK]

Common Mistakes:

• Confusing log M with n
• Assuming quadratic due to nested loops
• Counting 32^2 instead of 32

4. Consider the following buggy implementation of sum of two integers without + operator. Which line contains the subtle bug that causes incorrect results or infinite recursion?

medium

A. Line 3: base case condition if b == 0

B. Line 6: sum_ calculation using XOR and MASK

C. Line 8: recursive call with sum_ and carry

D. Line 7: carry calculation missing left shift

Solution

1. Step 1: Analyze carry calculation

   Carry must be (a & b) << 1 to shift carry bits to correct position.

2. Step 2: Identify missing left shift causes infinite recursion

   Without shifting, carry never reduces to zero, causing infinite recursion or wrong sum.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Carry missing shift breaks carry propagation [OK]

Hint: Carry must be shifted left by 1 bit [OK]

Common Mistakes:

• Forgetting carry shift
• Incorrect base case
• Not masking intermediate results

5. Suppose the problem is extended to find the bitwise AND of all numbers in the range [left, right], but now left and right can be negative integers. Which modification to the optimal algorithm is necessary?

hard

A. Convert negative numbers to their 2's complement positive equivalents and then apply the algorithm.

B. Use a mask to limit the bit-length and shift both numbers until equal, considering sign bits.

C. No modification needed; the existing bit-clearing approach works for negative numbers.

D. Iterate through the entire range because bitwise AND with negatives is undefined.

Solution

1. Step 1: Understand negative number representation

   Negative integers use 2's complement, so sign bits affect bitwise AND results.

2. Step 2: Modify approach

   Masking to limit bit-length and shifting both numbers until equal handles sign bits correctly and finds common prefix.

3. Step 3: Reject naive iteration

   Iterating entire range is inefficient and unnecessary; direct bitwise manipulation with sign awareness is needed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Handling sign bits requires masking and shifting, not naive bit-clearing [OK]

Hint: Handle sign bits with masking and shifting for negatives [OK]

Common Mistakes:

• Assuming algorithm works unchanged for negatives
• Trying to convert negatives to positives incorrectly
• Iterating entire range for negatives