Subsets Using Bitmask

📋

Problem

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.

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

Edge cases: Empty input array → output [[]]Single element array → output [[], [element]]Array with maximum allowed size (n=20) → ensure performance

</>

IDE

def subsets(nums: list[int]) -> list[list[int]]:public List<List<Integer>> subsets(int[] nums)vector<vector<int>> subsets(vector<int>& nums)function subsets(nums)

def subsets(nums):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    // Write your solution here
    return {};
}

function subsets(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Missing empty subset or subsetsNot including the empty subset or not enumerating all bitmasks from 0 to 2^n - 1.✅ Iterate bitmask from 0 to (1 << n) - 1 inclusive and include elements where bit i is set.

Wrong: Duplicate subsets or missing subsets with duplicates in inputAssuming input is unique but input contains duplicates; subsets generated by position cause duplicates.✅ Enforce input uniqueness before processing or handle duplicates by sorting and skipping duplicates.

Wrong: Subsets missing non-contiguous elements (greedy approach)Greedy approach that only picks contiguous or increasing elements, missing other subsets.✅ Use bitmask enumeration to generate all subsets regardless of element order.

Wrong: Timeout on large inputUsing exponential recursion without optimization or inefficient subset construction.✅ Use iterative bitmask enumeration and efficient data structures to avoid TLE.

✓

Test Cases

Try testing your code with empty and single-element inputs to catch base case bugs.

Consider inputs that might trick greedy or partial enumeration approaches.

Prepare for performance testing with maximum input size; optimize your enumeration method.

t1_01basic

Input{"nums":[1,2,3]}

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

⏱ Performance - must finish in 2000ms

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

💡 Think about how each bit in a number can represent whether to include an element.

💡 Use bitmask enumeration from 0 to 2^n - 1 to generate all subsets.

💡 For each bitmask, include nums[i] if the i-th bit is set.

Why it failed: Incorrect subsets generated - likely missing subsets or duplicates. Fix by enumerating all bitmasks from 0 to 2^n - 1 and including elements where bit i is set.

✓ Correctly enumerates all subsets using bitmask.

t1_02basic

Input{"nums":[4,5]}

Expected[[],[4],[5],[4,5]]

⏱ Performance - must finish in 2000ms

2 elements produce 2^2=4 subsets: empty, each single element, and both together.

💡 Number of subsets is 2^n; here n=2 so 4 subsets.

💡 Check bitmask from 0 to 3 and include elements accordingly.

💡 Ensure empty subset is included when bitmask is 0.

Why it failed: Missing subsets or incorrect subsets - likely off-by-one in bitmask range or incorrect bit checks. Fix by iterating bitmask from 0 to (1 << n) - 1 inclusive and checking each bit.

✓ All subsets generated correctly for small input.

t2_01edge

Input{"nums":[]}

Expected[[]]

⏱ Performance - must finish in 2000ms

Empty input array has exactly one subset: the empty subset.

💡 Consider what subsets exist when there are no elements.

💡 The power set of empty set is a set containing the empty set.

💡 Return [[]] when nums is empty.

Why it failed: Returned empty list instead of list containing empty subset. Fix by always including empty subset even if input is empty.

✓ Correctly returns [[]] for empty input.

t2_02edge

Input{"nums":[10]}

Expected[[],[10]]

⏱ Performance - must finish in 2000ms

Single element array has two subsets: empty and the element itself.

💡 With one element, subsets are empty and that element.

💡 Check bitmask 0 (empty) and 1 (include element).

💡 Ensure both subsets are included.

Why it failed: Only returned one subset or duplicates. Fix by enumerating bitmask from 0 to 1 and including element if bit 0 is set.

✓ Correctly handles single element input.

t2_03edge

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum allowed size n=20; 2^20=1,048,576 subsets. Must complete within time limit.

💡 Enumerating all subsets is O(n*2^n), which is feasible for n=20.

💡 Use efficient bitmask enumeration without recursion overhead.

💡 Avoid unnecessary copying; build subsets efficiently.

Why it failed: Solution times out due to exponential complexity. Optimize enumeration or use bitmask iteration instead of recursion.

✓ Handles maximum input size within time limit.

t3_01corner

Input{"nums":[1,2,2]}

Expected[[],[1],[1,2],[1,2,2],[1,2],[2],[2,2],[2]]

⏱ Performance - must finish in 2000ms

Input contains duplicates which violates problem constraints (unique elements). This test checks robustness. Expected output includes subsets with duplicates as per input positions.

💡 Input violates uniqueness constraint; test robustness of solution.

💡 Bitmask enumeration includes elements by position, so duplicates produce duplicate subsets.

💡 To avoid duplicates, input must be unique or preprocess to remove duplicates.

Why it failed: Code assumes unique input but input contains duplicates; duplicates in output subsets occur. Fix by enforcing unique input or filtering duplicates before processing.

✓ Handles or documents behavior with duplicates correctly.

t3_02corner

Input{"nums":[-1,0,1]}

Expected[[],[-1],[-1,0],[-1,0,1],[-1,1],[0],[0,1],[1]]

⏱ Performance - must finish in 2000ms

Input with negative and zero values; subsets include all combinations.

💡 Bitmask enumeration should not depend on element values.

💡 Check that negative or zero values are included correctly.

💡 Ensure no filtering or sign-based logic affects subset generation.

Why it failed: Incorrect subsets due to filtering or sign-based logic. Fix by enumerating subsets purely by bitmask without value checks.

✓ Correctly handles negative and zero values.

t3_03corner

Input{"nums":[1,2,3,4]}

Expected[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]

⏱ Performance - must finish in 2000ms

Test to catch greedy approach that picks subsets incorrectly (e.g., only subsets with increasing elements).

💡 Greedy approaches may miss subsets that skip elements.

💡 Bitmask enumeration includes all combinations regardless of order.

💡 Check that subsets like [2,4] or [1,3] are included.

Why it failed: Greedy approach misses subsets that skip elements. Fix by enumerating all bitmasks from 0 to 2^n - 1.

✓ All subsets including non-contiguous elements are generated.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum input size n=20; enumerating 2^20 subsets (1,048,576) must complete within 2 seconds.

💡 Use bitmask enumeration with efficient subset construction.

💡 Avoid recursion overhead by iterative bitmask loops.

💡 Preallocate memory or reuse data structures to reduce overhead.

Why it failed: TLE due to exponential complexity O(n*2^n). Optimize by using iterative bitmask enumeration and efficient data structures.

✓ Solution runs within time limit for n=20.

Practice

1. You are given an array where every element appears exactly twice except for one element that appears only once. Which approach guarantees finding the unique element in linear time and constant space?

easy

A. Using a dynamic programming approach to track element counts

B. Sorting the array and then scanning to find the unique element

C. Using a brute force nested loop to count occurrences of each element

D. Using XOR operation to cancel out duplicates and find the single element

Solution

1. Step 1: Understand problem constraints

   Every element except one appears twice, so duplicates cancel out under XOR.

2. Step 2: Identify approach that leverages XOR properties

   XOR of a number with itself is zero, and XOR with zero is the number itself, so XORing all elements leaves the unique one.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   XOR approach runs in O(n) time and O(1) space [OK]

Hint: XOR cancels duplicates perfectly [OK]

Common Mistakes:

• Sorting is O(n log n), not optimal
• Brute force is O(n²), inefficient
• DP is unrelated to this problem

2. Given the following Python code implementing sum of two integers without using + operator, what is the output when calling getSum(1, 2)?

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: First call getSum(1, 2)

   sum_ = (1 ^ 2) & MASK = 3, carry = ((1 & 2) << 1) & MASK = 0

2. Step 2: Since carry is 0, return sum_ = 3

   Base case reached, final sum is 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   1 + 2 = 3 matches output [OK]

Hint: XOR sum with carry zero returns final sum [OK]

Common Mistakes:

• Confusing carry calculation
• Off-by-one in recursion
• Returning carry instead of sum

3. The following code attempts to find the single number in an array using XOR. Identify the line containing the subtle bug that causes incorrect results.

medium

A. Line 2: Initializing result to nums[0] instead of 0

B. Line 4: Returning result without sorting

C. Line 3: Looping over nums including the first element again

D. Line 1: Function definition

Solution

1. Step 1: Analyze initialization of result

   Result initialized to nums[0], then XORed again with nums[0] in loop, cancelling it out incorrectly.

2. Step 2: Understand correct initialization

   Result should start at 0 so XOR accumulates all elements exactly once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initializing to zero avoids double XOR of first element [OK]

Hint: XOR accumulator must start at zero [OK]

Common Mistakes:

• Initializing with first element causes double XOR
• Loop includes first element again
• Misplaced return statement

4. Suppose you want to count the number of set bits for all integers from 0 to n, but now n can be negative as well (e.g., from -n to n). Which modification to the Brian Kernighan's bit counting approach correctly handles this scenario?

hard

A. Apply the same algorithm directly to negative numbers since bitwise operations work the same.

B. Skip negative numbers because bit counting is undefined for them.

C. Convert negative numbers to their two's complement 32-bit unsigned representation before counting bits.

D. Use string conversion of the absolute value of negative numbers and count '1's.

Solution

1. Step 1: Understand bit representation of negatives

   Negative integers are represented in two's complement form, so counting bits requires interpreting them as unsigned 32-bit integers.

2. Step 2: Modify algorithm accordingly

   Convert negative numbers to their 32-bit unsigned equivalent before applying Kernighan's trick to count set bits correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two's complement conversion ensures correct bit counting for negatives [OK]

Hint: Negative bits require two's complement conversion [OK]

Common Mistakes:

• Applying algorithm directly to negatives
• Ignoring negatives
• Using absolute value without conversion

5. Suppose the input array can contain negative integers as well as positive integers. Which modification to the trie-based maximum XOR algorithm is necessary to correctly handle negative numbers?

hard

A. No modification needed; XOR works the same for negative numbers.

B. Convert all numbers to their 32-bit unsigned representation before inserting and querying the trie.

C. Use 64-bit representation instead of 32-bit to cover sign bits.

D. Use absolute values of numbers before inserting into the trie.

Solution

1. Step 1: Understand negative number representation

   Negative numbers use two's complement, so their bit patterns differ from unsigned integers.

2. Step 2: Convert to unsigned 32-bit representation

   By masking with 0xFFFFFFFF, negative numbers become unsigned 32-bit integers, allowing consistent trie insertion and XOR calculation.

3. Step 3: Avoid using absolute values or larger bit widths

   Absolute values lose sign info; larger bit widths are unnecessary and inefficient.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Unsigned 32-bit masking ensures correct bitwise trie operations [OK]

Hint: Mask negatives to unsigned 32-bit for trie [OK]

Common Mistakes:

• Ignoring sign bits
• Using absolute values
• Assuming 64-bit needed