Interview Prepbit-manipulationmediumAmazonGoogleFacebook

Subsets Using Bitmask

Choose your preparation mode4 modes available

Try It Solution Trace

▶

Steps

setup

Initialize / Setup

Start with an empty subset represented by bitmask 0 (all bits cleared). The input array [1,2,3] is sorted (already sorted).

💡 Starting with an empty subset is the base case for building all subsets recursively.

Line:

nums.sort()
res = []
backtrack(0, [])

💡 The empty subset corresponds to bitmask 000 (binary), meaning no elements included.

insert

Add empty subset to results

Add the current subset (empty) to the results list. This corresponds to bitmask 000.

💡 Every subset, including empty, must be added to results to ensure completeness.

Line:res.append(path[:])

💡 The empty subset is the first subset in the output.

expand

Include element 1 (index 0)

Include the first element (1) in the subset by setting bit 0 (LSB) to 1, updating bitmask to 001 (decimal 1).

💡 Setting bit 0 means including the first element in the subset.

Line:path.append(nums[i])

💡 Bitmask 001 means subset includes element at index 0 (value 1).

insert

Add subset [1] to results

Add the subset containing only element 1 (bitmask 001) to the results.

💡 Every formed subset is added immediately to results.

Line:res.append(path[:])

💡 Subset [1] corresponds to bitmask 001.

expand

Include element 2 (index 1)

Include the second element (2) by setting bit 1 to 1, updating bitmask from 001 to 011 (decimal 3).

💡 Setting bit 1 means including element at index 1 in the subset.

Line:path.append(nums[i])

💡 Bitmask 011 means subset includes elements at indices 0 and 1 (values 1 and 2).

insert

Add subset [1,2] to results

Add the subset containing elements 1 and 2 (bitmask 011) to the results.

💡 Adding subsets as soon as they are formed ensures all subsets are captured.

Line:res.append(path[:])

💡 Subset [1,2] corresponds to bitmask 011.

expand

Include element 3 (index 2)

Include the third element (3) by setting bit 2 to 1, updating bitmask from 011 to 111 (decimal 7).

💡 Setting bit 2 means including element at index 2 in the subset.

Line:path.append(nums[i])

💡 Bitmask 111 means subset includes all elements (1,2,3).

insert

Add subset [1,2,3] to results

Add the full subset containing elements 1, 2, and 3 (bitmask 111) to the results.

💡 The full subset is the last subset formed in this branch.

Line:res.append(path[:])

💡 Subset [1,2,3] corresponds to bitmask 111.

shrink

Backtrack: Remove element 3 (index 2)

Backtrack by removing element 3 from the subset, clearing bit 2, updating bitmask from 111 to 011 (decimal 3).

💡 Backtracking removes the last included element to explore other subsets.

Line:path.pop()

💡 Clearing bit 2 means excluding element 3 again.

expand

Exclude element 3 and include element 2 (index 2) alone

Backtrack further to explore subsets excluding element 1 but including element 3 alone, setting bit 2 to 1 and clearing bits 1 and 0.

💡 Exploring subsets that include element 3 but exclude earlier elements.

Line:path.append(nums[i])

💡 Bitmask 100 (decimal 4) means subset includes only element 3.

insert

Add subset [3] to results

Add the subset containing only element 3 (bitmask 100) to the results.

💡 Subsets with single elements are also added.

Line:res.append(path[:])

💡 Subset [3] corresponds to bitmask 100.

expand

Include element 1 and 3 (indices 0 and 2)

Include elements 1 and 3 by setting bits 0 and 2 to 1, bitmask becomes 101 (decimal 5).

💡 Combining non-adjacent elements by setting corresponding bits.

Line:path.append(nums[i])

💡 Bitmask 101 means subset includes elements at indices 0 and 2 (values 1 and 3).

insert

Add subset [1,3] to results

Add the subset containing elements 1 and 3 (bitmask 101) to the results.

💡 All subsets with any combination of elements are added.

Line:res.append(path[:])

💡 Subset [1,3] corresponds to bitmask 101.

expand

Include element 2 and 3 (indices 1 and 2)

Include elements 2 and 3 by setting bits 1 and 2 to 1, bitmask becomes 110 (decimal 6).

💡 Including adjacent elements 2 and 3 by setting bits 1 and 2.

Line:path.append(nums[i])

💡 Bitmask 110 means subset includes elements at indices 1 and 2 (values 2 and 3).

insert

Add subset [2,3] to results

Add the subset containing elements 2 and 3 (bitmask 110) to the results.

💡 All subsets with two elements are included.

Line:res.append(path[:])

💡 Subset [2,3] corresponds to bitmask 110.

shrink

Backtrack to empty subset

Backtrack by removing all included elements, clearing bits 0,1,2, returning bitmask to 000 (decimal 0).

💡 Backtracking resets subset to empty to explore remaining subsets.

Line:path.pop()

💡 Clearing all bits means starting fresh for new subset exploration.

expand

Include element 2 (index 1) alone

Include only element 2 by setting bit 1 to 1, bitmask becomes 010 (decimal 2).

💡 Exploring subsets starting with element 2 alone.

Line:path.append(nums[i])

💡 Bitmask 010 means subset includes only element 2.

insert

Add subset [2] to results

Add the subset containing only element 2 (bitmask 010) to the results.

💡 Single element subsets are added as well.

Line:res.append(path[:])

💡 Subset [2] corresponds to bitmask 010.

reconstruct

Backtrack complete, all subsets generated

All subsets have been generated and added to results. The recursion ends.

💡 The algorithm completes after exploring all inclusion/exclusion paths.

Line:return res

💡 All 8 subsets correspond to bitmasks 000 through 111.

def subsets(nums):  # STEP 1: Initialize
    nums.sort()  # STEP 1
    res = []  # STEP 1
    def backtrack(start, path):  # STEP 2
        res.append(path[:])  # STEP 2: Add current subset
        for i in range(start, len(nums)):  # STEP 3: Iterate elements
            path.append(nums[i])  # STEP 3: Include element
            backtrack(i + 1, path)  # STEP 4: Recurse
            path.pop()  # STEP 5: Backtrack
    backtrack(0, [])  # STEP 1: Start recursion
    return res  # STEP 19: Return all subsets

if __name__ == '__main__':
    print(subsets([1,2,3]))  # Driver code

📊

Subsets Using Bitmask - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the bitmask corresponds to subset inclusion, making the abstract recursion concrete and easy to follow.

Step 1/19

·Active fill★Answer cell

Initialize empty subset

────────────────

💡 Bitmask 000 means no elements included yet.

Add subset to results

────────────────

💡 Empty subset corresponds to bitmask 000.

Include element 1

────

💡 Bit 0 set means element 1 included.

Add subset to results

────

💡 Subset [1] added.

Include element 2

──────

💡 Bits 1 and 0 set mean elements 1 and 2 included.

Add subset to results

──────

💡 Subset [1,2] added.

Include element 3

────────

💡 Bits 2,1,0 set mean all elements included.

Add subset to results

────────

💡 Full subset added.

Backtrack remove element 3

💡 Bit 2 cleared, subset back to [1,2].

Include element 3 alone

────────

💡 Bit 2 set, bits 1 and 0 cleared.

Add subset to results

────────

💡 Subset [3] added.

Include elements 1 and 3

────────

💡 Bits 2 and 0 set, bit 1 cleared.

Add subset to results

────────

💡 Subset [1,3] added.

Include elements 2 and 3

────────

💡 Bits 2 and 1 set, bit 0 cleared.

Add subset to results

────────

💡 Subset [2,3] added.

Backtrack clear all

💡 Bitmask reset to empty subset.

Include element 2 alone

──────

💡 Bit 1 set means element 2 included.

Add subset to results

──────

💡 Subset [2] added.

Complete recursion

💡 All subsets generated.

Key Takeaways

✓ Each subset corresponds exactly to a bitmask where each bit indicates inclusion of an element.

This insight is hard to see from code alone because the bitmask representation is implicit in recursion.

✓ The recursion explores subsets by including or excluding elements, which corresponds to setting or clearing bits in the bitmask.

Visualizing bit changes clarifies how recursion builds subsets step-by-step.

✓ Backtracking removes elements by clearing bits, allowing exploration of all subset combinations without repetition.

Seeing bits cleared during backtracking concretely shows how the algorithm reverses decisions.

Practice

(1/5)

1. Given the following Python code to generate Gray code sequence, what is the output of grayCode(2)?

easy

A. [1, 0, 3, 2]

B. [0, 1, 2, 3]

C. [0, 1, 3, 2]

D. [0, 2, 3, 1]

Solution

Step 1: Compute values for i in range(4)
For i=0: 0 ^ (0>>1)=0; i=1: 1 ^ (0)=1; i=2: 2 ^ (1)=2^1=3; i=3: 3 ^ (1)=3^1=2
Step 2: Collect results in list
The sequence is [0, 1, 3, 2], which matches the Gray code property.
Final Answer:
Option C -> Option C
Quick Check:
Manual XOR calculation confirms the sequence [0,1,3,2] [OK]

Hint: XOR with right-shifted index generates Gray code directly [OK]

Common Mistakes:

Confusing the order of XOR and shift
Off-by-one errors in range leading to missing or extra elements
Misinterpreting the output as binary numbers instead of integers

2. Consider the following code snippet that finds the single number in an array using XOR. What is the value of result after processing the third element in the input [2, 3, 2]?

easy

A. 3

B. 1

C. 0

D. 2

Solution

Step 1: Trace result after first element (2)
result = 0 · 2 = 2
Step 2: Trace result after second element (3)
result = 2 · 3 = 1
Step 3: Trace result after third element (2)
result = 1 · 2 = 3
Final Answer:
Option A -> Option A
Quick Check:
Final XOR result is 3, the unique element [OK]

Hint: XOR accumulates unique element progressively [OK]

Common Mistakes:

Off-by-one in loop iteration
Confusing XOR with addition
Misreading variable updates

3. You are given a sequence of integers representing bytes. You need to verify if this sequence forms a valid encoding where each character can be 1 to 4 bytes long, and continuation bytes must start with bits '10'. Which approach best guarantees an efficient and correct validation?

easy

A. Use a greedy approach that always assumes the longest possible character at each step.

B. Use a brute force approach checking each byte with nested conditions for all possible byte patterns.

C. Use dynamic programming to store valid prefixes and build up to the full sequence.

D. Use a single pass with a counter tracking how many continuation bytes are expected next.

Solution

Step 1: Understand the problem constraints
The problem requires validating UTF-8 encoding where each character can be 1 to 4 bytes, and continuation bytes must start with '10'.
Step 2: Identify the approach that efficiently tracks continuation bytes
The single pass with a continuation byte counter efficiently tracks how many continuation bytes are expected, ensuring correctness and O(n) time.
Final Answer:
Option D -> Option D
Quick Check:
Single pass with counter matches UTF-8 rules and is optimal [OK]

Hint: Track continuation bytes with a counter for linear validation [OK]

Common Mistakes:

Assuming greedy longest match always works
Using DP unnecessarily complicates the problem

4. What is the time complexity of generating an n-bit Gray code sequence using the optimal bitwise formula [i ^ (i >> 1) for i in range(1 << n)]?

medium

A. O(n)

B. O((2^n)!)

C. O(n * 2^n)

D. O(2^n)

Solution

Step 1: Analyze the loop iteration count
The list comprehension iterates over all integers from 0 to 2^n - 1, so 2^n iterations.
Step 2: Analyze work per iteration
Each iteration performs constant time bitwise operations (XOR and right shift), so O(1) per iteration.
Final Answer:
Option D -> Option D
Quick Check:
Total time is proportional to 2^n, not multiplied by n or factorial [OK]

Hint: Loop runs 2^n times with O(1) work each [OK]

Common Mistakes:

Confusing n with 2^n and claiming O(n)
Assuming bitwise operations cost O(n)
Mistaking factorial complexity from brute force backtracking

5. Identify the bug in the following code snippet for Single Number II using the bitwise FSM approach:

medium

A. Line with 'twos |= ones & num'

B. Line with 'ones ^= num'

C. Line with 'common_mask = ~(ones | twos)'

D. Line with 'ones &= common_mask'

Solution

Step 1: Compare common_mask calculation with correct formula
The correct mask is the negation of the AND of ones and twos, i.e., ~(ones & twos), not ~(ones | twos).
Step 2: Understand impact of wrong mask
Using OR instead of AND causes bits to be cleared incorrectly, failing to reset bits appearing thrice properly.
Final Answer:
Option C -> Option C
Quick Check:
Correct mask uses AND, not OR, to clear bits appearing three times [OK]

Hint: Mask must clear bits appearing in both ones and twos simultaneously [OK]

Common Mistakes:

Using OR instead of AND in mask
Misordering bit updates

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Initialize / Setup

Add empty subset to results

Include element 1 (index 0)

Add subset [1] to results

Include element 2 (index 1)

Add subset [1,2] to results

Include element 3 (index 2)

Add subset [1,2,3] to results

Backtrack: Remove element 3 (index 2)

Exclude element 3 and include element 2 (index 2) alone

Add subset [3] to results

Include element 1 and 3 (indices 0 and 2)

Add subset [1,3] to results

Include element 2 and 3 (indices 1 and 2)

Add subset [2,3] to results

Backtrack to empty subset

Include element 2 (index 1) alone

Add subset [2] to results

Backtrack complete, all subsets generated

Key Takeaways

Practice

Solution

Step 1: Compute values for i in range(4)

Step 2: Collect results in list

Final Answer:

Quick Check:

Solution

Step 1: Trace result after first element (2)

Step 2: Trace result after second element (3)

Step 3: Trace result after third element (2)

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that efficiently tracks continuation bytes

Final Answer:

Quick Check:

Solution

Step 1: Analyze the loop iteration count

Step 2: Analyze work per iteration

Final Answer:

Quick Check:

Solution

Step 1: Compare common_mask calculation with correct formula

Step 2: Understand impact of wrong mask

Final Answer:

Quick Check:

Ready to prove it?