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. Consider the following Python code implementing the optimal backtracking solution for Combination Sum II. What is the final returned list when calling combinationSum2([1,2,2], 4)?

easy

A. [[1,2,2]]

B. [[1,2],[2]]

C. [[1,2],[2,2]]

D. [[1,2],[2,2],[1,2,2]]

Solution

1. Step 1: Sort candidates and start backtracking

   Sorted candidates: [1,2,2]. Start from index 0 with target=4.

2. Step 2: Explore combinations skipping duplicates at same level

   Try 1 -> target=3, then try 2 at next index -> target=1, next 2 is duplicate at same level skipped. No further candidates fit. Backtrack and try 2 at index 1 -> target=2, next 2 at index 2 -> target=0, add [2,2]. Both [1,2,2] and [2,2] are valid unique combinations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both [1,2,2] and [2,2] sum to 4 without reuse and duplicates skipped [OK]

Hint: Duplicate skipping prevents repeated combinations [OK]

Common Mistakes:

• Including partial sums like [2]
• Allowing reuse of elements
• Not skipping duplicates at same recursion level

2. Consider the following Python code implementing combination sum with reuse allowed:

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)
    backtrack(0, [], target)
    return result

print(combinationSum([2,3,6,7], 7))

What is the exact output of this code?

easy

A. [[7]]

B. [[2, 2, 3], [7]]

C. [[2, 2, 3]]

D. [[7], [2, 2, 3]]

Solution

1. Step 1: Trace backtrack calls for candidates=[2,3,6,7], target=7

   Sorted candidates: [2,3,6,7]. The function tries counts of 2 from 0 to 3 (max_use=3), then recurses on next index. Valid combinations found are [7] and [2,2,3].

2. Step 2: Check order of results appended

   Backtracking explores index 0 with counts 0..3, then index 1, so [7] is found after [2,2,3]. The result list appends [7] first, then [2,2,3]. But since the code appends when target==0, the order is [[7], [2, 2, 3]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected combinations with correct order [OK]

Hint: Order depends on recursion path, not sorted output [OK]

Common Mistakes:

• Assuming output is sorted by combination length or lex order
• Missing one valid combination

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

4. You are given an unsorted array of positive integers. Your task is to find the largest subset such that for every pair (Si, Sj) in the subset, either Si divides Sj or Sj divides Si. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Greedy approach by always picking the smallest element and adding divisible elements afterwards

B. Use a brute force backtracking to generate all subsets and check divisibility

C. Sort the array and use dynamic programming to build the longest chain where each element divides the next

D. Use a graph traversal to find the largest clique where edges represent divisibility

Solution

1. Step 1: Understand problem constraints

   The problem requires a subset where every pair is divisible in one direction, which suggests a chain-like structure.

2. Step 2: Identify suitable algorithm

   Sorting the array allows divisibility checks to be done efficiently in increasing order, enabling dynamic programming to build the longest divisible chain.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + DP is classic for largest divisible subset [OK]

Hint: Sort + DP builds longest divisible chain [OK]

Common Mistakes:

• Greedy fails because local choices don't guarantee global maximum
• Brute force is correct but inefficient, not practical
• Graph clique approach is incorrect because divisibility is not symmetric

5. Examine the following buggy code snippet for letter case permutation. Which line contains the subtle bug that causes incorrect results on inputs with digits?

def letterCasePermutation(s: str) -> List[str]:
    res = []
    arr = list(s)
    def backtrack(i: int):
        if i == len(arr):
            res.append(''.join(arr))
            return
        if arr[i].isdigit():
            arr[i] = arr[i].upper()  # BUG: digits have no case
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()
            backtrack(i + 1)
            arr[i] = arr[i].upper()
            backtrack(i + 1)
            arr[i] = s[i]
    backtrack(0)
    return res

medium

A. Line with 'if i == len(arr):'

B. Line with 'arr[i] = arr[i].upper() # BUG: digits have no case'

C. Line with 'if arr[i].isdigit():'

D. Line with 'arr[i] = s[i]' to revert changes

Solution

1. Step 1: Analyze digit handling

   Digits have no uppercase or lowercase forms, so calling upper() on a digit is unnecessary and incorrect.

2. Step 2: Identify bug impact

   Modifying digits causes incorrect permutations or corrupted results; digits should be left unchanged and recursion called directly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Digits must be skipped, not toggled [OK]

Hint: Digits must not be modified or toggled [OK]

Common Mistakes:

• Forgetting to revert changes
• Modifying digits as letters