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. You are given a list of candidate numbers (which may contain duplicates) and a target sum. You need to find all unique combinations where each candidate number is used at most once and the sum of the combination equals the target. Which algorithmic approach best guarantees finding all unique combinations without duplicates efficiently?

easy

A. Backtracking with sorting candidates, skipping duplicates at the same recursion level, and pruning branches when the candidate exceeds the remaining target

B. Greedy algorithm that picks the largest candidates first until the target is met or exceeded

C. Dynamic programming subset-sum approach without handling duplicates explicitly

D. Brute force recursion without sorting or duplicate checks, exploring all subsets

Solution

1. Step 1: Understand problem constraints

   The problem requires unique combinations without reuse and no duplicate results, so duplicates must be handled carefully.

2. Step 2: Identify suitable algorithm

   Backtracking with sorting and skipping duplicates at the same recursion level ensures no repeated combinations. Early pruning avoids unnecessary recursion when candidates exceed the target.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + duplicate skipping + pruning is the standard approach [OK]

Hint: Sorting and skipping duplicates avoids repeated combinations [OK]

Common Mistakes:

• Using greedy misses some combinations
• DP without duplicate handling outputs duplicates
• Brute force is correct but inefficient and duplicates appear

2. Consider the following Python code implementing the optimal backtracking with bitmask and memoization approach for the Matchsticks to Square problem. Given the input [1,1,2,2,2], what is the final return value of makesquare([1,1,2,2,2])?

easy

A. True

B. Depends on the order of matchsticks

C. Raises an exception due to index error

D. False

Solution

1. Step 1: Calculate total and side length

   Total = 1+1+2+2+2 = 8, side = 8/4 = 2.

2. Step 2: Trace backtracking calls

   Sorted sticks: [2,2,2,1,1]. The algorithm tries to form sides of length 2. It can form three sides with three 2's, and the last side with two 1's. Hence, returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum divisible by 4 and sticks fit sides exactly [OK]

Hint: Sum divisible by 4 and sticks fit sides exactly [OK]

Common Mistakes:

• Forgetting to sort and prune
• Assuming order affects result
• Miscounting sides formed

3. Consider the following code snippet implementing the trie-based solution for counting valid words for puzzles. Given the words = ["apple", "plea", "plead"] and puzzles = ["aelwxyz"], what is the returned count for this puzzle?

easy

A. [1]

B. [0]

C. [2]

D. [3]

Solution

1. Step 1: Compute bitmasks for words

   "apple" -> letters {a,p,l,e}, mask with ≤7 bits; "plea" and "plead" similarly processed.

2. Step 2: Check puzzle "aelwxyz"

   First letter 'a' must be in word; words "apple" and "plea" contain 'a' and are subsets of puzzle letters; "plead" contains 'd' not in puzzle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two words match conditions [OK]

Hint: Count words containing puzzle first letter and subset of puzzle letters [OK]

Common Mistakes:

• Counting words missing first letter
• Including words with letters outside puzzle
• Off-by-one in counting matches

4. Suppose you want to generate all combinations of size k from numbers 1 to n, but now elements can be reused multiple times in a combination (combinations with replacement). Which modification to the backtracking approach correctly handles this?

hard

A. Use iterative lexicographic generation without any changes

B. Change the recursive call to backtrack(i + 1, path) to prevent reuse of elements

C. Change the recursive call to backtrack(i, path) to allow reuse of the current element

D. Sort the input array before backtracking to handle duplicates

Solution

1. Step 1: Understand combinations with replacement allow repeated elements

   To allow reuse, the recursive call must not increment start index beyond current element.

2. Step 2: Modify recursion to backtrack(i, path) to allow current element reuse

   This ensures the same element can be chosen multiple times in subsequent recursive calls.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using backtrack(i, path) enables combinations with replacement [OK]

Hint: Reuse requires recursive calls with same start index [OK]

Common Mistakes:

• Incrementing start index prevents element reuse

5. Suppose the problem is modified so that each element in the array can be used multiple times to form the k equal sum subsets (i.e., unlimited reuse of elements). Which modification to the backtracking with bitmask memoization approach is necessary to correctly solve this variant?

hard

A. Keep bitmask but allow resetting bits after each recursive call

B. Sort ascending instead of descending to handle reuse properly

C. Use the same code without changes because bitmask handles reuse implicitly

D. Remove bitmask usage since elements can be reused; track counts instead

Solution

1. Step 1: Understand reuse impact on state representation

   Bitmask tracks used elements uniquely; with reuse allowed, usage state is not binary but counts.

2. Step 2: Modify approach accordingly

   Bitmask must be removed or replaced by frequency counts to track how many times each element is used; otherwise, states are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask cannot represent multiple uses of same element [OK]

Hint: Bitmask tracks usage once; reuse breaks this assumption [OK]

Common Mistakes:

• Trying to reuse bitmask for multiple uses
• Ignoring state representation changes