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. You need to generate all unique groups of size k from numbers 1 to n without repetition, where order within each group does not matter. Which algorithmic approach guarantees generating all such groups efficiently without duplicates?

easy

A. Backtracking that explores all number choices with pruning to avoid duplicates

B. Greedy selection picking the smallest available number until group size is reached

C. Dynamic programming to count subsets but not generate them explicitly

D. Sorting all numbers and then selecting consecutive sequences of length k

Solution

1. Step 1: Understand the problem requires all unique combinations of size k from n numbers

   Greedy or sorting consecutive sequences do not guarantee all unique combinations without duplicates.

2. Step 2: Backtracking with pruning systematically explores all valid combinations and avoids duplicates by controlling start indices

   This approach ensures all unique groups are generated efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with pruning is the standard approach for combinations [OK]

Hint: Backtracking with pruning avoids duplicates efficiently [OK]

Common Mistakes:

• Thinking greedy or sorting consecutive sequences generate all combinations

2. Consider the following Python code implementing the optimal backtracking with bitmask and memoization approach for the Matchsticks to Square problem. Given the input [1,1,2,2,2], what is the final return value of makesquare([1,1,2,2,2])?

easy

A. True

B. Depends on the order of matchsticks

C. Raises an exception due to index error

D. False

Solution

1. Step 1: Calculate total and side length

   Total = 1+1+2+2+2 = 8, side = 8/4 = 2.

2. Step 2: Trace backtracking calls

   Sorted sticks: [2,2,2,1,1]. The algorithm tries to form sides of length 2. It can form three sides with three 2's, and the last side with two 1's. Hence, returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum divisible by 4 and sticks fit sides exactly [OK]

Hint: Sum divisible by 4 and sticks fit sides exactly [OK]

Common Mistakes:

• Forgetting to sort and prune
• Assuming order affects result
• Miscounting sides formed

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

4. Consider the following Python code for generating subsets with duplicates. What is the value of res after processing the input [1, 2, 2]?

easy

A. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

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

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

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

Solution

1. Step 1: Trace iterations for input [1, 2, 2]

   Start with res = [[]]. - i=0 (num=1): s=0, start=1, add [1] -> res = [[], [1]] - i=1 (num=2): s=0, start=2, add [2], [1,2] -> res = [[], [1], [2], [1,2]] - i=2 (num=2): duplicate, s=start from previous iteration=2, start=4, add [2,2], [1,2,2] -> res = [[], [1], [2], [1,2], [2,2], [1,2,2]]

2. Step 2: Confirm final res matches option

   The final res contains exactly these subsets without duplicates: [], [1], [2], [1,2], [2,2], [1,2,2].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected unique subsets for input [1,2,2] [OK]

Hint: Duplicate skips start index to avoid repeats [OK]

Common Mistakes:

• Appending duplicates multiple times by resetting s=0 always
• Off-by-one errors in start index
• Including extra subsets from previous iterations

5. The following code attempts to count subsets with sum K using space-optimized DP. Identify the line that contains a subtle bug that can cause incorrect results.

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(num, K + 1):
            dp[j] += dp[j - num]
    return dp[K]

medium

A. for j in range(num, K + 1):

B. dp[0] = 1

C. dp = [0] * (K + 1)

D. dp[j] += dp[j - num]

Solution

1. Step 1: Analyze iteration order

   The inner loop iterates forward from num to K, which causes dp[j] to use updated dp values from the same iteration, leading to overcounting.

2. Step 2: Correct iteration direction

   To avoid overcounting, the inner loop must iterate backward from K down to num.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration in DP causes incorrect counts -> bug in loop range [OK]

Hint: Inner loop must iterate backward to avoid reuse of updated dp values [OK]

Common Mistakes:

• Using forward iteration in space-optimized DP
• Misunderstanding dp update dependencies