Subsets II (With Duplicates)

▶

Steps

setup

Sort the input array

The input array [1,2,2] is sorted to group duplicates together, resulting in [1,2,2].

💡 Sorting is crucial because it allows the algorithm to detect duplicates by comparing adjacent elements.

Line:

nums.sort()

💡 Duplicates appear consecutively, enabling the algorithm to skip redundant subset extensions.

setup

Initialize result with empty subset

Initialize the result list with an empty subset: res = [[]].

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

Line:

res = [[]]

💡 All subsets will be built by extending this initial empty subset.

fill_row

Process first element: 1

Start iterating over nums. For i=0 (element 1), since it's the first element, set s=0 to extend all existing subsets.

💡 For the first element, we extend all subsets because there are no duplicates to consider yet.

Line:

if i > 0 and nums[i] == nums[i - 1]:
    s = start
else:
    s = 0

💡 The variable s determines which subsets to extend; here, all subsets are extended.

fill_cells

Extend subsets with 1

Extend all subsets from index s=0 to end by adding 1. res becomes [[], [1]].

💡 Adding 1 to each subset creates new subsets including 1.

Line:

for j in range(s, len(res)):
    res.append(res[j] + [nums[i]])

💡 Subsets grow by including the current element.

fill_row

Update start index after processing 1

Update start to current length of res, start = 2, to mark the start of new subsets created in this iteration.

💡 Tracking start helps identify which subsets to extend for duplicates.

Line:

start = len(res)

💡 start marks the boundary between old and new subsets.

fill_row

Process second element: 2 (first occurrence)

For i=1 (element 2), since nums[1] != nums[0], set s=0 to extend all subsets.

💡 For a new element different from previous, extend all subsets.

Line:

if i > 0 and nums[i] == nums[i - 1]:
    s = start
else:
    s = 0

💡 All subsets are extended with this new element.

fill_cells

Extend subsets with 2 (first occurrence)

Extend all subsets from s=0 to end by adding 2. res becomes [[], [1], [2], [1,2]].

💡 Adding 2 to all subsets creates new subsets including 2.

Line:

for j in range(s, len(res)):
    res.append(res[j] + [nums[i]])

💡 Subsets now include those with and without 2.

fill_row

Update start index after processing first 2

Update start to current length of res, start = 4, marking new subsets created in this iteration.

💡 This start index will help skip extending old subsets for the next duplicate 2.

Line:

start = len(res)

💡 start separates old subsets from new subsets created by adding the first 2.

fill_row

Process third element: 2 (duplicate)

For i=2 (element 2), since nums[2] == nums[1], set s = start = 4 to extend only subsets created in previous iteration.

💡 To avoid duplicates, only extend subsets created by adding the previous 2.

Line:

if i > 0 and nums[i] == nums[i - 1]:
    s = start
else:
    s = 0

💡 This selective extension prevents generating duplicate subsets.

fill_cells

Extend subsets with 2 (duplicate)

Extend subsets from index s=4 to end by adding 2. res becomes [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]].

💡 Only subsets created by the previous 2 are extended to avoid duplicates.

Line:

for j in range(s, len(res)):
    res.append(res[j] + [nums[i]])

💡 This step adds subsets with the second 2 without duplicating subsets from earlier.

fill_row

Update start index after processing second 2

Update start to current length of res, start = 6, marking all subsets created.

💡 This marks the final boundary of subsets created.

Line:

start = len(res)

💡 All subsets have been generated at this point.

reconstruct

Return the final list of subsets

Return the result list containing all unique subsets: [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]].

💡 The algorithm completes by returning all subsets generated without duplicates.

Line:

return res

💡 The final output contains all unique subsets including those with duplicates handled.

from typing import List

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()  # STEP 1: Sort input to group duplicates
    res = [[]]  # STEP 2: Initialize result with empty subset
    start = 0
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:  # STEP 3,6,9: Check for duplicates
            s = start  # Use start to skip old subsets
        else:
            s = 0  # Extend all subsets for new element
        start = len(res)  # STEP 5,8,11: Update start to mark new subsets
        for j in range(s, len(res)):  # STEP 4,7,10: Extend subsets
            res.append(res[j] + [nums[i]])
    return res  # STEP 12: Return all unique subsets

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

📊

Subsets II (With Duplicates) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how sorting and selective extension of subsets prevent duplicates, which is hard to grasp from code alone.

enteringnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

enteringnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Found 1: []

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

s=0

Found 1: []

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

extended subsets with 1

Found 2: [] [1]

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

start updated to 2

Found 2: [] [1]

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

s=0

Found 2: [] [1]

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

extended subsets with 2

Found 4: [2] [1,2]

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

start updated to 4

Found 4: [2] [1,2]

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

s=4

Found 4: [2] [1,2]

choosingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

extended subsets with duplicate 2

Found 6: [2,2] [1,2,2]

backtrackingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Tried

start updated to 6

Found 6: [2,2] [1,2,2]

backtrackingnums=[1,2,2]

Call Path (current → root)

subsetsWithDup([1,2,2])

Found 6: [2,2] [1,2,2]

Key Takeaways

✓ Sorting the input array is essential to group duplicates and enable skipping redundant subset extensions.

Without sorting, detecting duplicates would be complex and error-prone.

✓ The 'start' index marks the boundary between old and new subsets, allowing selective extension to avoid duplicates.

This mechanism is subtle and hard to understand without visualizing how subsets grow.

✓ When a duplicate element is encountered, only subsets created in the previous iteration are extended to prevent duplicate subsets.

This selective extension is the key decision that ensures uniqueness of subsets.

Practice

1. Consider the following code snippet implementing the trie-based solution for counting valid words for puzzles. Given the words = ["apple", "plea", "plead"] and puzzles = ["aelwxyz"], what is the returned count for this puzzle?

easy

A. [1]

B. [0]

C. [2]

D. [3]

Solution

1. Step 1: Compute bitmasks for words

   "apple" -> letters {a,p,l,e}, mask with ≤7 bits; "plea" and "plead" similarly processed.

2. Step 2: Check puzzle "aelwxyz"

   First letter 'a' must be in word; words "apple" and "plea" contain 'a' and are subsets of puzzle letters; "plead" contains 'd' not in puzzle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two words match conditions [OK]

Hint: Count words containing puzzle first letter and subset of puzzle letters [OK]

Common Mistakes:

• Counting words missing first letter
• Including words with letters outside puzzle
• Off-by-one in counting matches

2. The following code attempts to solve Combination Sum II but contains a subtle bug. Identify the line causing the bug.

medium

A. Line with 'if i > start and candidates[i] == candidates[i-1]: continue' for duplicate skipping

B. Line with 'if candidates[i] > target: break' for pruning

C. Line with 'backtrack(i + 1, path + [candidates[i]], target - candidates[i])' recursive call

D. Line with 'prev = candidates[i]' inside the loop

Solution

1. Step 1: Understand duplicate skipping logic

   The code uses 'if i > start and candidates[i] == candidates[i-1]: continue' to skip duplicates correctly.

2. Step 2: Identify subtle bug

   The 'prev' variable is assigned but never used, which is redundant and may confuse readers. The actual duplicate skipping is done by the index comparison, so 'prev' should be removed to avoid confusion.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Redundant 'prev' variable assignment is a subtle bug causing confusion [OK]

Hint: Duplicate skipping must be consistent and correct at recursion level; remove unused variables [OK]

Common Mistakes:

• Using prev variable incorrectly
• Skipping duplicates globally instead of per recursion level
• Not pruning when candidate > target

3. What is the time complexity of the space-optimized DP solution for counting subsets with sum K, given an array of size n and target sum K?

medium

A. O(2^n) because all subsets are explored

B. O(n * K) because the DP iterates over n elements and sums up to K

C. O(n + K) because it processes each element and sum once

D. O(n * K^2) because nested loops iterate over n and K twice

Solution

1. Step 1: Identify loops in the DP

   Outer loop runs n times, inner loop runs up to K times for each element.

2. Step 2: Calculate total operations

   Total operations = n * K, so time complexity is O(n * K).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP iterates over all elements and sums up to K -> O(n * K) [OK]

Hint: DP complexity depends on n and K, not exponential [OK]

Common Mistakes:

• Confusing DP with brute force exponential time
• Assuming linear time due to single loops

4. What is the time complexity of the optimal backtracking solution for letter case permutation on a string of length n with k letters (non-digit characters)?

medium

A. O(2^k * n) because only letters toggle case and each permutation requires joining n characters

B. O(2^k * k) because only letters are toggled and digits are skipped

C. O(n * 2^n) because each character doubles the permutations

D. O(n^2) because of nested recursion and string concatenation

Solution

1. Step 1: Identify branching factor

   Only letters (k of them) cause branching, each with 2 choices, so total permutations are 2^k.

2. Step 2: Calculate work per permutation

   Each permutation requires joining n characters to form a string, so O(n) per permutation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is exponential in letters, linear in string length [OK]

Hint: Complexity depends on letters, not total length [OK]

Common Mistakes:

• Assuming all characters double permutations
• Ignoring join cost per permutation

5. Suppose you want to generate all subsets of nums but now elements can be reused unlimited times in each subset (i.e., multisets). Which modification to the backtracking approach correctly handles this?

hard

A. At each recursion step, recurse twice: once including current element and staying at same index to allow reuse, once excluding and moving to next index

B. At each recursion step, recurse with index + 1 only, excluding current element to avoid duplicates

C. Use bit manipulation as before, but allow bits to be set multiple times to represent reuse

D. Sort the array and use two pointers to generate subsets with repeated elements

Solution

1. Step 1: Understand reuse requirement

   Allowing unlimited reuse means after including an element, we can include it again without advancing index.

2. Step 2: Modify recursion accordingly

   Recurse twice: include current element and recurse with same index, or exclude and recurse with next index.

3. Step 3: Why other options fail

   At each recursion step, recurse with index + 1 only, excluding current element to avoid duplicates excludes reuse by always advancing index; Use bit manipulation as before, but allow bits to be set multiple times to represent reuse is invalid as bitmask can't represent multiple counts; Sort the array and use two pointers to generate subsets with repeated elements is unrelated.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Staying at same index after include enables repeated elements [OK]

Hint: Reuse means recurse with same index after include [OK]

Common Mistakes:

• Advancing index after include prevents reuse
• Trying bitmask for multisets