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 need to generate all unique groups of size k from numbers 1 to n without repetition, where order within each group does not matter. Which algorithmic approach guarantees generating all such groups efficiently without duplicates?

easy

A. Backtracking that explores all number choices with pruning to avoid duplicates

B. Greedy selection picking the smallest available number until group size is reached

C. Dynamic programming to count subsets but not generate them explicitly

D. Sorting all numbers and then selecting consecutive sequences of length k

Solution

1. Step 1: Understand the problem requires all unique combinations of size k from n numbers

   Greedy or sorting consecutive sequences do not guarantee all unique combinations without duplicates.

2. Step 2: Backtracking with pruning systematically explores all valid combinations and avoids duplicates by controlling start indices

   This approach ensures all unique groups are generated efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with pruning is the standard approach for combinations [OK]

Hint: Backtracking with pruning avoids duplicates efficiently [OK]

Common Mistakes:

• Thinking greedy or sorting consecutive sequences generate all combinations

2. What is the time complexity of the backtracking solution with frequency counting for the Combination Sum (Reuse Allowed) problem, where N is the number of candidates, T is the target, and M is the minimum candidate value?

medium

A. O(N * T) because each candidate is tried once for each target value.

B. O(2^N) because each candidate can be either included or excluded once.

C. O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M.

D. O(T^N) because for each target value, all candidates are tried in all combinations.

Solution

1. Step 1: Identify recursion depth and branching factor

   The recursion depth is roughly T/M because the smallest candidate can be used up to T/M times. At each level, up to N candidates are considered with multiple counts.

2. Step 2: Calculate total number of recursive calls

   Each candidate can be chosen 0 to max_use times, leading to branching factor roughly N^(T/M + 1). This exponential complexity dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exponential branching with depth proportional to T/M matches O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M. [OK]

Hint: Exponential in target divided by smallest candidate [OK]

Common Mistakes:

• Confusing DP complexity with backtracking
• Ignoring exponential branching due to reuse

3. What is the time complexity of the optimal backtracking solution for letter case permutation on a string of length n with k letters (non-digit characters)?

medium

A. O(2^k * n) because only letters toggle case and each permutation requires joining n characters

B. O(2^k * k) because only letters are toggled and digits are skipped

C. O(n * 2^n) because each character doubles the permutations

D. O(n^2) because of nested recursion and string concatenation

Solution

1. Step 1: Identify branching factor

   Only letters (k of them) cause branching, each with 2 choices, so total permutations are 2^k.

2. Step 2: Calculate work per permutation

   Each permutation requires joining n characters to form a string, so O(n) per permutation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is exponential in letters, linear in string length [OK]

Hint: Complexity depends on letters, not total length [OK]

Common Mistakes:

• Assuming all characters double permutations
• Ignoring join cost per permutation

4. The following code attempts to generate all unique subsets from an array with duplicates. Which line contains a subtle bug that causes incorrect or duplicate subsets?

medium

A. Line 9: if i > 0 and nums[i] == nums[i - 1]: s = 0

B. Line 13: res.append(res[j] + [nums[i]])

C. Line 11: start = len(res)

D. Line 6: nums.sort()

Solution

1. Step 1: Understand the role of variable s

   Variable s determines the start index for adding new subsets. For duplicates, s should be set to the previous start to avoid duplicates.

2. Step 2: Identify the bug in line 9

   Setting s = 0 for duplicates causes subsets to be appended from the beginning, generating duplicate subsets. The correct logic is to set s = start (previous length) to skip duplicates only at the same recursion level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect s causes duplicate subsets [OK]

Hint: Duplicate skipping must use previous start index [OK]

Common Mistakes:

• Setting s=0 always for duplicates
• Not sorting input before processing
• Appending without proper start index

5. Suppose the problem changes: now each element in the input array can be chosen multiple times (unlimited reuse), and duplicates still exist. Which modification to the iterative approach correctly generates all unique subsets with duplicates and unlimited reuse?

hard

A. Keep the same code but remove the duplicate skipping condition to allow reuse.

B. Sort the array, and for each element, always start from index 0 when adding new subsets to allow reuse, but skip duplicates at the same recursion level.

C. Sort the array, and for each element, start from the previous start index for duplicates, but allow reuse by appending to all existing subsets including newly added ones in the same iteration.

D. Use backtracking with a visited array to track reuse and skip duplicates by sorting.

Solution

1. Step 1: Understand unlimited reuse impact

   Unlimited reuse means subsets can include the same element multiple times, so the iteration must consider all existing subsets each time.

2. Step 2: Modify iteration start index

   To allow reuse, always start from index 0 when adding new subsets, so elements can be appended multiple times. However, duplicates must still be skipped at the same recursion level to avoid repeated subsets.

3. Step 3: Confirm skipping duplicates at recursion level

   Skipping duplicates at the same recursion level prevents generating identical subsets multiple times despite reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Starting from 0 allows reuse; skipping duplicates avoids repeats [OK]

Hint: Start from 0 to allow reuse; skip duplicates at recursion level [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Starting from previous start index blocks reuse
• Using visited array unnecessarily complicates iterative approach