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. You are given a list of candidate numbers (which may contain duplicates) and a target sum. You need to find all unique combinations where each candidate number is used at most once and the sum of the combination equals the target. Which algorithmic approach best guarantees finding all unique combinations without duplicates efficiently?

easy

A. Backtracking with sorting candidates, skipping duplicates at the same recursion level, and pruning branches when the candidate exceeds the remaining target

B. Greedy algorithm that picks the largest candidates first until the target is met or exceeded

C. Dynamic programming subset-sum approach without handling duplicates explicitly

D. Brute force recursion without sorting or duplicate checks, exploring all subsets

Solution

1. Step 1: Understand problem constraints

   The problem requires unique combinations without reuse and no duplicate results, so duplicates must be handled carefully.

2. Step 2: Identify suitable algorithm

   Backtracking with sorting and skipping duplicates at the same recursion level ensures no repeated combinations. Early pruning avoids unnecessary recursion when candidates exceed the target.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + duplicate skipping + pruning is the standard approach [OK]

Hint: Sorting and skipping duplicates avoids repeated combinations [OK]

Common Mistakes:

• Using greedy misses some combinations
• DP without duplicate handling outputs duplicates
• Brute force is correct but inefficient and duplicates appear

2. What is the worst-case time complexity of the optimized dynamic programming solution for the Largest Divisible Subset problem, where n is the number of elements in the input array?

medium

A. O(n^2) due to nested loops checking divisibility pairs

B. O(2^n) because all subsets are considered

C. O(n^3) because of triple nested loops for subset checks

D. O(n log n) due to sorting and linear DP

Solution

1. Step 1: Identify main operations

   Sorting takes O(n log n). The DP uses two nested loops: outer loop over n elements, inner loop up to i elements.

2. Step 2: Analyze nested loops

   Each pair (i,j) is checked once, resulting in O(n^2) divisibility checks. Early break may speed up in practice but worst case remains O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP nested loops dominate complexity [OK]

Hint: DP nested loops -> O(n^2) worst case [OK]

Common Mistakes:

• Confusing sorting time as dominant (O(n log n))
• Assuming triple nested loops due to subset checks
• Thinking brute force complexity applies to DP

3. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium

A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset

B. O(2^n) because there are 2^n subsets and each subset is generated in constant time

C. O(n^2) because of nested loops over n elements

D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements

Solution

1. Step 1: Identify outer loop complexity

   The outer loop runs 2^n times, once per subset mask.

2. Step 2: Identify inner loop complexity

   For each mask, the inner loop iterates n times to check each bit.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is 2^n * n due to mask and bit checks [OK]

Hint: Each subset requires checking n bits -> O(n*2^n) [OK]

Common Mistakes:

• Assuming subset generation is O(2^n) ignoring bit checks
• Confusing n^2 with 2^n * n

4. Suppose the problem is modified so that elements can be chosen multiple times (unlimited reuse) to form subsets. Which approach correctly adapts to count the number of max bitwise-OR subsets under this new constraint?

hard

A. Use dynamic programming over OR values with state compression to count combinations

B. Use backtracking with memoization to handle repeated elements and prune search

C. Use the same bitmask enumeration approach since subsets remain finite

D. Sort elements and greedily pick those with highest bits until max OR is reached

Solution

1. Step 1: Recognize infinite subsets due to unlimited reuse

   Bitmask enumeration is infeasible as subsets are infinite with reuse allowed.

2. Step 2: Use DP over OR states to count combinations efficiently

   DP with state compression tracks counts of subsets achieving each OR value, handling reuse.

3. Step 3: Understand greedy or naive backtracking fail due to infinite or redundant subsets

   Greedy misses combinations; naive backtracking is exponential and inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP over OR states handles reuse -> correct and efficient [OK]

Hint: Reuse means infinite subsets -> DP over OR states needed [OK]

Common Mistakes:

• Trying bitmask enumeration despite infinite subsets
• Using greedy approach ignoring subset counts

5. Suppose the problem changes: now you can use each element in the array unlimited times to form subsets summing to K (i.e., unlimited repetitions allowed). Which modification to the space-optimized DP code below correctly counts the number of such subsets?

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

Choose the correct range for the inner loop to handle unlimited usage of elements.

hard

A. for j in range(K, num - 1, -1): # iterate backward

B. for j in range(K + 1): # iterate forward including invalid indices

C. for j in range(0, K + 1): # iterate forward from 0

D. for j in range(num, K + 1): # iterate forward

Solution

1. Step 1: Understand unlimited usage impact

   When elements can be reused unlimited times, the inner loop must iterate forward to allow multiple counts of the same element.

2. Step 2: Choose correct iteration range

   Iterating forward from num to K ensures dp[j] accumulates counts including repeated usage of num.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Forward iteration enables unlimited reuse of elements in subset sums [OK]

Hint: Unlimited usage requires forward iteration to accumulate counts correctly [OK]

Common Mistakes:

• Using backward iteration which prevents reuse
• Starting loop from 0 causing invalid indices