Subsets

▶

Steps

setup

Initialize variables

We start by determining the length of the input list and initializing an empty list to hold all subsets.

💡 Knowing the input size is essential to calculate how many subsets exist (2^n). The result list will store all subsets generated.

Line:

n = len(nums)
result = []

💡 The number of subsets depends on the input size; initializing result prepares to collect answers.

traverse

Start first bitmask iteration (mask=0)

Begin iterating over bitmasks from 0 to 7 (2^3 - 1). The first bitmask is 0, representing the empty subset.

💡 Each bitmask encodes which elements to include; 0 means include none.

Line:

for mask in range(1 << n):
    subset = []

💡 The empty subset is always included as the first subset.

compare

Check bit 0 for mask=0

Check if the least significant bit of mask 0 is set to include nums[0]. It is not set, so nums[0] is excluded.

💡 Each bit corresponds to an element; checking bits decides inclusion.

Line:

for i in range(n):
    if mask & (1 << i):
        subset.append(nums[i])

💡 Bit 0 controls inclusion of the first element; here it is off, so no inclusion.

compare

Check bit 1 for mask=0

Check bit 1 of mask 0 to decide inclusion of nums[1]. It is not set, so nums[1] is excluded.

💡 Systematic bit checks ensure all elements are considered for inclusion.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 Bit 1 corresponds to the second element; it is off, so exclude.

compare

Check bit 2 for mask=0

Check bit 2 of mask 0 to decide inclusion of nums[2]. It is not set, so nums[2] is excluded.

💡 Completing bit checks finalizes subset construction for this mask.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 Bit 2 corresponds to the third element; it is off, so exclude.

insert

Add subset [] to result

The subset built from mask 0 is empty. Add it to the result list.

💡 Adding subsets as they are built collects all answers.

Line:

result.append(subset)

💡 The empty subset is the first valid subset.

traverse

Start next bitmask iteration (mask=1)

Move to mask 1 (binary 001), which includes only the first element.

💡 Each mask represents a unique subset; mask 1 includes nums[0].

Line:

for mask in range(1 << n):
    subset = []

💡 Mask 1 will build subset [1].

compare

Check bit 0 for mask=1

Check bit 0 of mask 1; it is set, so include nums[0] = 1 in subset.

💡 Bit set means include corresponding element.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 Bit 0 set means first element is included.

compare

Check bit 1 for mask=1

Check bit 1 of mask 1; it is not set, so exclude nums[1].

💡 Bit not set means exclude element.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 Bit 1 off means second element excluded.

compare

Check bit 2 for mask=1

Check bit 2 of mask 1; it is not set, so exclude nums[2].

💡 Final bit check completes subset construction.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 Bit 2 off means third element excluded.

insert

Add subset [1] to result

Add the subset [1] built from mask 1 to the result list.

💡 Collecting subsets as they are built accumulates the final answer.

Line:

result.append(subset)

💡 Subset [1] is now part of the solution set.

traverse

Start bitmask iteration (mask=2)

Move to mask 2 (binary 010), which includes only the second element.

💡 Mask 2 will build subset [2].

Line:

for mask in range(1 << n):
    subset = []

💡 Systematic iteration continues to cover all subsets.

compare

Check bit 0 for mask=2

Bit 0 of mask 2 is not set, exclude nums[0].

💡 Bit off means exclude element.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 First element excluded for this subset.

compare

Check bit 1 for mask=2

Bit 1 of mask 2 is set, include nums[1] = 2.

💡 Bit set means include element.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 Second element included in subset.

compare

Check bit 2 for mask=2

Bit 2 of mask 2 is not set, exclude nums[2].

💡 Completing bit checks finalizes subset.

Line:

if mask & (1 << i):
    subset.append(nums[i])

💡 Third element excluded.

insert

Add subset [2] to result

Add the subset [2] to the result list.

💡 Collecting subsets builds the final answer.

Line:

result.append(subset)

💡 Subset [2] is now part of the solution set.

traverse

Process remaining masks (3 to 7) similarly

The algorithm continues iterating masks 3 to 7, building subsets by checking bits and adding them to the result.

💡 Each mask uniquely encodes a subset; systematic iteration ensures all subsets are generated.

Line:

for mask in range(1 << n):
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(nums[i])
    result.append(subset)

💡 All subsets are generated by interpreting bits of each mask.

reconstruct

Complete all subsets and return result

After processing all masks, the result list contains all subsets. The function returns this list.

💡 Returning the collected subsets completes the algorithm.

Line:

return result

💡 The final answer is the complete power set of the input.

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    n = len(nums)  # STEP 1: Initialize n
    result = []    # STEP 1: Initialize result
    for mask in range(1 << n):  # STEP 2: Iterate over all bitmasks
        subset = []  # STEP 2: Start building subset
        for i in range(n):  # STEP 3: Check each bit
            if mask & (1 << i):  # STEP 3: If bit set, include nums[i]
                subset.append(nums[i])
        result.append(subset)  # STEP 4: Add subset to result
    return result  # STEP 18: Return all subsets

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

📊

Subsets - Watch the Algorithm Execute, Step by Step

Watching each bitmask and subset construction step reveals how binary representation maps directly to subset inclusion, making the concept of subsets concrete and intuitive.

enteringnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Remaining

mask in range(0,8)

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Remaining

mask=0 to 7

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 excluded

Remaining

bit 1bit 2

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 excludedbit 1 excluded

Remaining

bit 2

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 excludedbit 1 excludedbit 2 excluded

backtrackingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

mask=0 processed

Remaining

mask=1 to 7

Found 1: []

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

mask=0 processed

Remaining

mask=1 to 7

Found 1: []

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 included

Remaining

bit 1bit 2

Partial: [1]

Found 1: []

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 includedbit 1 excluded

Remaining

bit 2

Partial: [1]

Found 1: []

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 includedbit 1 excludedbit 2 excluded

Partial: [1]

Found 1: []

backtrackingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

mask=0 processedmask=1 processed

Remaining

mask=2 to 7

Found 2: [] [1]

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

mask=0 processedmask=1 processed

Remaining

mask=2 to 7

Found 2: [] [1]

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 excluded

Remaining

bit 1bit 2

Found 2: [] [1]

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 excludedbit 1 included

Remaining

bit 2

Partial: [2]

Found 2: [] [1]

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

bit 0 excludedbit 1 includedbit 2 excluded

Partial: [2]

Found 2: [] [1]

backtrackingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

mask=0 processedmask=1 processedmask=2 processed

Remaining

mask=3 to 7

Found 3: [1] [2]

choosingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

mask=0 processedmask=1 processedmask=2 processed

Remaining

mask=3mask=4mask=5mask=6mask=7

Found 3: [1] [2]

backtrackingnums=[1,2,3]

Call Path (current → root)

subsets([1,2,3])

Tried

mask=0 processedmask=1 processedmask=2 processedmask=3 processedmask=4 processedmask=5 processedmask=6 processedmask=7 processed

Found 8: [2,3] [1,2,3]

Key Takeaways

✓ Each subset corresponds exactly to a unique bitmask from 0 to 2^n - 1.

This insight is hard to see from code alone because the binary representation connection is implicit, but the visualization makes it explicit.

✓ Checking each bit in the mask systematically decides inclusion or exclusion of each element.

Seeing each bit checked one by one clarifies how subsets are constructed element-by-element.

✓ The algorithm exhaustively enumerates all subsets without pruning, ensuring completeness.

Understanding that no subsets are skipped helps learners trust the algorithm's correctness.

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 are given a string containing letters and digits. You need to generate all possible strings by toggling the case of each letter independently, while digits remain unchanged. Which algorithmic approach guarantees generating all valid permutations efficiently?

easy

A. Backtracking with include/exclude choices for each letter's case

B. Sorting the string and then generating permutations by swapping adjacent characters

C. Dynamic programming using a bottom-up table to store partial permutations

D. Greedy algorithm that toggles letters only when it reduces the lexicographical order

Solution

1. Step 1: Understand problem constraints

   The problem requires exploring all combinations of letter cases, which is a classic subsets problem where each letter can be included as lowercase or uppercase.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude choices for each letter's case systematically explores all 2^k combinations, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all subsets of letter cases [OK]

Hint: Toggle letter cases via backtracking subsets [OK]

Common Mistakes:

• Thinking greedy can find all permutations
• Using DP that doesn't fit subsets pattern

3. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

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

B. Greedy algorithm that picks the largest elements first and assigns them to subsets

C. Backtracking with bitmask memoization to explore subsets and prune invalid states

D. Sorting and then using a sliding window to find equal sum partitions

Solution

1. Step 1: Understand problem constraints and complexity

   The problem requires partitioning into exactly k subsets with equal sums, which is NP-complete and requires exploring combinations exhaustively.

2. Step 2: Evaluate algorithm suitability

   Greedy and sliding window approaches fail to guarantee correctness because they don't explore all combinations. Simple DP without pruning is inefficient and incomplete. Backtracking with bitmask memoization efficiently prunes and caches states, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking with memoization handles all subsets optimally [OK]

Hint: Bitmask memoization prunes repeated subset states [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Confusing subset sum DP with partitioning into k subsets

4. Consider the following Python function implementing backtracking with bitmask memoization for partitioning an array into k equal sum subsets. Given nums = [4, 3, 2, 3, 5, 2, 1] and k = 4, what is the final return value of canPartitionKSubsets(nums, k)?

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target sum

   Total sum is 4+3+2+3+5+2+1=20, target per subset = 20/4=5.

2. Step 2: Trace backtracking with sorted nums

   Sorted nums: [5,4,3,3,2,2,1]. The algorithm finds subsets: {5}, {4,1}, {3,2}, {3,2} all summing to 5, so returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All subsets sum to target, so partition possible [OK]

Hint: Sum divisible by k and backtracking finds valid subsets [OK]

Common Mistakes:

• Miscounting sum or target
• Assuming no solution due to order

5. The following code attempts to solve the Matchsticks to Square problem using backtracking with bitmask and memoization. Identify the line containing the subtle bug that can cause incorrect results or infinite recursion.

medium

A. Line with 'if total % 4 != 0: return false' (no divisibility check)

B. Line with 'matchsticks.sort(reverse=true)' (missing sorting causes inefficiency)

C. Line with 'memo[(used_mask, curr_sum, sides_formed)] = false' (incorrect memoization)

D. Line with recursive call 'backtrack(next_mask, next_sum, sides_formed)' missing return statement

Solution

1. Step 1: Identify missing return in recursion

   The recursive call without return means the function ignores successful paths, causing incorrect results or infinite recursion.

2. Step 2: Confirm other lines are correct

   Divisibility check is present, sorting is done, and memoization line is correct for caching failures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing return in recursive call breaks backtracking correctness [OK]

Hint: Missing return in recursive call breaks correctness [OK]

Common Mistakes:

• Forgetting to return recursive call result
• Skipping divisibility check
• Not sorting before backtracking