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 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

2. You need to generate all possible subsets of a given set of distinct integers. Which algorithmic approach guarantees enumerating every subset exactly once, including the empty subset, without missing or duplicating any subset?

easy

A. Greedy algorithm that picks elements based on a heuristic to maximize subset size

B. Dynamic programming approach that builds subsets by summing elements to target values

C. Backtracking with include/exclude decisions at each element to explore all subset combinations

D. Sorting the array and then using two pointers to find pairs that form subsets

Solution

1. Step 1: Understand problem requirements

   The problem requires enumerating all subsets, which means exploring all combinations of including or excluding each element.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude decisions systematically explores all subsets without duplication or omission, including the empty subset.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking ensures all subsets are generated [OK]

Hint: Include/exclude backtracking covers all subsets [OK]

Common Mistakes:

• Confusing subset generation with greedy or DP sum problems

3. What is the time complexity of the space-optimized DP solution for counting subsets with sum K, given an array of size n and target sum K?

medium

A. O(2^n) because all subsets are explored

B. O(n * K) because the DP iterates over n elements and sums up to K

C. O(n + K) because it processes each element and sum once

D. O(n * K^2) because nested loops iterate over n and K twice

Solution

1. Step 1: Identify loops in the DP

   Outer loop runs n times, inner loop runs up to K times for each element.

2. Step 2: Calculate total operations

   Total operations = n * K, so time complexity is O(n * K).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP iterates over all elements and sums up to K -> O(n * K) [OK]

Hint: DP complexity depends on n and K, not exponential [OK]

Common Mistakes:

• Confusing DP with brute force exponential time
• Assuming linear time due to single loops

4. 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

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