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. Consider the following Python code implementing the optimal backtracking solution for Combination Sum III. What is the final value of res after calling combinationSum3(3, 7)?

easy

A. [[1, 2, 4]]

B. [[1, 3, 3]]

C. [[2, 2, 3]]

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls for k=3, n=7

   Start from 1, try combinations of size 3 summing to 7. Valid combos are [1,2,4] only because 1+2+4=7.

2. Step 2: Verify no other combos meet criteria

   Other combos like [1,3,3] or [2,2,3] are invalid due to duplicates or sum mismatch.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only [1,2,4] sums to 7 with 3 distinct numbers [OK]

Hint: Only distinct numbers summing to 7 with size 3 is [1,2,4] [OK]

Common Mistakes:

• Including duplicates like [1,3,3]
• Miscounting sum or size

2. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

3. Consider the following Python code that generates all subsets of nums = [1, 2, 3]. What is the value of subset when mask = 5 during the iteration?

easy

A. [1, 3]

B. [2, 3]

C. [1, 2]

D. [3]

Solution

1. Step 1: Convert mask=5 to binary

   5 in binary is 101, meaning bits 0 and 2 are set.

2. Step 2: Map bits to indices in nums

   Bit 0 corresponds to nums[0]=1, bit 2 corresponds to nums[2]=3, so subset = [1, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mask 5 selects elements at positions 0 and 2 -> [1, 3] [OK]

Hint: Mask bits correspond to included elements [OK]

Common Mistakes:

• Off-by-one bit indexing
• Confusing mask bits with element values

4. What is the time complexity of the optimal bitmask + trie solution for the Number of Valid Words for Each Puzzle problem, given W words with average length L, and P puzzles?

medium

A. O(W * L + P * M), where M is the average number of trie nodes traversed per puzzle

B. O(W * P * L), since each word is checked against each puzzle

C. O(W * 2^7 + P * 7), enumerating all subsets of puzzle letters for each puzzle

D. O(W * L * 26 + P * 26), traversing trie nodes for all letters

Solution

1. Step 1: Analyze word insertion

   Each word is converted to a bitmask and inserted into trie in O(L) time, total O(W * L).

2. Step 2: Analyze puzzle queries

   For each puzzle, dfs traverses trie nodes corresponding to subsets of puzzle letters, average M nodes, total O(P * M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known optimal complexity [OK]

Hint: Trie traversal depends on subsets of puzzle letters, not all words [OK]

Common Mistakes:

• Assuming brute force complexity
• Confusing 2^7 subsets with trie traversal nodes
• Ignoring average trie traversal cost

5. The following backtracking code attempts to generate all subsets of nums. What is the subtle bug causing incorrect output?

medium

A. Using global variable without resetting between calls

B. Not copying the current subset before appending to result causes all subsets to be the same list

C. Base case missing the empty subset

D. Forgetting to pop after including an element causes subsets to accumulate extra elements

Solution

1. Step 1: Analyze base case append

   The code appends path directly without copying, so all appended references point to the same mutable list.

2. Step 2: Consequence of mutation

   As recursion unwinds and path changes, all entries in result reflect the final state of path, causing incorrect subsets.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy (path[:]) fixes the bug [OK]

Hint: Always append a copy of the current path to result [OK]

Common Mistakes:

• Forgetting to pop after append
• Misunderstanding base case inclusion