Subsets Using Bitmask

▶

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.

Initialize empty subset

A

0

0

0

0

0

0

0

0

=0

B

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

=

0

0

0

0

0

0

0

0

=0

💡 Bitmask 000 means no elements included yet.

Add subset to results

A

0

0

0

0

0

0

0

0

=0

B

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

=

0

0

0

0

0

0

0

0

=0

💡 Empty subset corresponds to bitmask 000.

Include element 1

A

0

1

=1

B

────

=

0

1

=1

💡 Bit 0 set means element 1 included.

Add subset to results

A

0

1

=1

B

────

=

0

1

=1

💡 Subset [1] added.

Include element 2

A

0

1

1

=3

B

──────

=

0

1

1

=3

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

Add subset to results

A

0

1

1

=3

B

──────

=

0

1

1

=3

💡 Subset [1,2] added.

Include element 3

A

0

1

1

1

=7

B

────────

=

0

1

1

1

=7

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

Add subset to results

A

0

1

1

1

=7

B

────────

=

0

1

1

1

=7

💡 Full subset added.

Backtrack remove element 3

A

0

1

1

=3

B

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

Include element 3 alone

A

0

1

0

0

=4

B

────────

=

0

1

0

0

=4

💡 Bit 2 set, bits 1 and 0 cleared.

Add subset to results

A

0

1

0

0

=4

B

────────

=

0

1

0

0

=4

💡 Subset [3] added.

Include elements 1 and 3

A

0

1

0

1

=5

B

────────

=

0

1

0

1

=5

💡 Bits 2 and 0 set, bit 1 cleared.

Add subset to results

A

0

1

0

1

=5

B

────────

=

0

1

0

1

=5

💡 Subset [1,3] added.

Include elements 2 and 3

A

0

1

1

0

=6

B

────────

=

0

1

1

0

=6

💡 Bits 2 and 1 set, bit 0 cleared.

Add subset to results

A

0

1

1

0

=6

B

────────

=

0

1

1

0

=6

💡 Subset [2,3] added.

Backtrack clear all

A

0

0

0

0

0

0

0

0

=0

B

💡 Bitmask reset to empty subset.

Include element 2 alone

A

0

1

0

=2

B

──────

=

0

1

0

=2

💡 Bit 1 set means element 2 included.

Add subset to results

A

0

1

0

=2

B

──────

=

0

1

0

=2

💡 Subset [2] added.

Complete recursion

A

0

0

0

0

0

0

0

0

=0

B

💡 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. You are given an array of positive integers and a target sum K. You need to find how many subsets of the array sum exactly to K. Which of the following approaches guarantees an optimal solution with polynomial time complexity?

easy

A. Greedy algorithm that picks the largest elements first until the sum reaches or exceeds K

B. Pure recursion that tries all subsets without memoization

C. Dynamic Programming using a bottom-up tabulation approach that counts subsets for all sums up to K

D. Sorting the array and using two pointers to find pairs that sum to K

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all subsets summing to K, which involves exploring combinations, not just pairs or greedy picks.

2. Step 2: Evaluate approaches

   Greedy and two-pointer methods fail because they do not consider all subsets. Pure recursion is correct but exponential. Bottom-up DP efficiently counts subsets for all sums up to K, ensuring polynomial time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP tabulation counts subsets for all sums -> polynomial time [OK]

Hint: Counting subsets with sum K requires DP, not greedy or two-pointer [OK]

Common Mistakes:

• Assuming greedy or two-pointer works for subset sums
• Confusing counting subsets with finding pairs

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. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?

easy

A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.

B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.

C. Dynamic programming based on subset sums without pruning or memoization.

D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.

Solution

1. Step 1: Understand problem constraints

   The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.

2. Step 2: Identify suitable algorithm

   Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + memoization prunes repeated states [OK]

Hint: Bitmask + memoization prunes repeated states [OK]

Common Mistakes:

• Assuming greedy always works for partitioning
• Confusing DP without pruning as efficient
• Ignoring memoization benefits

4. You are given a list of words and a list of puzzles, each puzzle being a string of 7 unique letters. For each puzzle, you need to count how many words satisfy two conditions: the word contains the puzzle's first letter, and all letters of the word are contained within the puzzle. Which approach guarantees an optimal solution for this problem?

easy

A. Use bitmasking to represent words and puzzles, combined with a trie to efficiently count valid words for each puzzle.

B. Use a brute force approach checking each word against each puzzle with set containment checks.

C. Use a dynamic programming approach to count subsets of puzzle letters matching words.

D. Use a greedy approach selecting words that share the most letters with puzzles.

Solution

1. Step 1: Understand problem constraints

   The problem requires checking subsets of puzzle letters and matching words efficiently, which is expensive with brute force.

2. Step 2: Identify optimal approach

   Bitmasking encodes letters as bits, and a trie built on word bitmasks allows fast traversal of valid subsets, ensuring efficient counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + trie approach is known optimal for this problem [OK]

Hint: Bitmask + trie efficiently enumerates subsets [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using DP without bitmasking
• Greedy approaches fail on subset constraints

5. Suppose the problem is modified so that letters can be toggled multiple times, allowing reuse of characters in permutations (e.g., toggling the same letter case multiple times in different positions). Which modification to the backtracking approach correctly handles this variant without generating duplicates?

hard

A. Use a visited set to track permutations and skip duplicates after generation

B. Modify recursion to allow toggling letters multiple times but prune branches that revisit the same index

C. Change the algorithm to generate permutations with replacement by increasing recursion depth beyond string length

D. Use iterative BFS with a queue that enqueues toggled strings and avoids revisiting states

Solution

1. Step 1: Understand reuse variant

   Allowing reuse means letters can be toggled multiple times in different positions, increasing state space and possible duplicates.

2. Step 2: Identify correct approach

   Iterative BFS with a queue can track states and avoid revisiting duplicates efficiently, unlike naive recursion which may generate duplicates or infinite loops.

3. Step 3: Why other options fail

   Visited sets after generation are inefficient; pruning recursion by index doesn't prevent reuse; increasing recursion depth breaks problem constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   BFS with state tracking handles reuse and duplicates [OK]

Hint: Use BFS with visited states to handle reuse [OK]

Common Mistakes:

• Trying to prune recursion by index only
• Ignoring duplicates generated by reuse