Subsets II (With Duplicates)

📋

Subsets II (With Duplicates)

Edge cases:

</>

IDE

def subsetsWithDup(nums: list[int]) -> list[list[int]]:public List<List<Integer>> subsetsWithDup(int[] nums)vector<vector<int>> subsetsWithDup(vector<int>& nums)function subsetsWithDup(nums)

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    // Write your solution here
    return {};
}

function subsetsWithDup(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[], [1], [2], [1, 2], [2, 2], [1, 2, 2], [2, 2]]Duplicate subsets present due to not skipping duplicates at the same recursion level.✅ Add condition to skip nums[i] if nums[i] == nums[i-1] and i > start index in backtracking loop.

Wrong: []Empty output due to not handling empty input or base case correctly.✅ Return [[]] when input is empty or add base case to add current path when index == len(nums).

Wrong: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2], [2, 2, 2]]Missing subsets due to greedy skipping of some branches in recursion.✅ Explore both include and exclude branches for each element; skip duplicates only at same recursion level.

Wrong: [[], [2], [2, 2], [2, 2, 2], [2, 2, 2]]Duplicate subsets due to not sorting input before recursion.✅ Sort input array before starting backtracking to group duplicates.

Wrong: Timeout or no outputExponential time complexity without pruning duplicates causes TLE.✅ Implement skip condition for duplicates at same recursion level and prune recursion branches.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before tackling duplicates.

Ensure your duplicate skipping logic is precise and only skips duplicates at the same recursion level.

Optimize your backtracking to prune duplicate branches efficiently to handle large inputs.

t1_01basic

Input{"nums":[1,2,2]}

Expected[[],[1],[1,2],[1,2,2],[2],[2,2]]

⏱ Performance - must finish in 2000ms

Starting from an empty subset, we include or exclude each element. Sorting helps group duplicates so we skip repeated subsets at the same recursion depth.

💡 Think about generating subsets by including or excluding each element.

💡 Sort the array first and skip duplicates at the same recursion depth to avoid repeated subsets.

💡 Use backtracking with a condition to skip nums[i] if it's the same as nums[i-1] and i > start index.

Why it failed: Output missing subsets or contains duplicates due to not sorting or not skipping duplicates at the same recursion level. Fix by sorting input and skipping duplicates when nums[i] == nums[i-1] and i > start.

✓ Correct subsets generated with duplicates properly skipped.

t1_02basic

Input{"nums":[1,2,3]}

Expected[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

⏱ Performance - must finish in 2000ms

All subsets of [1,2,3] with no duplicates, total 8 subsets.

💡 Generate all subsets by include/exclude decisions for each element.

💡 No duplicates here, but sorting still helps maintain order.

💡 Backtracking with no skip needed since no duplicates.

Why it failed: Missing subsets or duplicates due to incorrect recursion or skipping logic. Fix by proper backtracking including all elements.

✓ All subsets generated correctly without duplicates.

t2_01edge

Input{"nums":[]}

Expected[[]]

⏱ Performance - must finish in 2000ms

Empty input array returns only the empty subset.

💡 Consider the base case when input is empty.

💡 The power set of empty set is a set containing empty set.

💡 Return [[]] immediately or handle base case in recursion.

Why it failed: Output missing empty subset or returns empty list due to not handling empty input. Fix by returning [[]] when nums is empty.

✓ Correctly returns [[]] for empty input.

t2_02edge

Input{"nums":[2]}

Expected[[],[2]]

⏱ Performance - must finish in 2000ms

Single element input returns empty subset and subset with that element.

💡 Check behavior with single element input.

💡 Subsets are empty set and set containing the single element.

💡 Backtracking should handle single element correctly.

Why it failed: Missing subsets or duplicates due to incorrect base case or recursion. Fix by ensuring single element subsets are included.

✓ Correct subsets generated for single element input.

t2_03edge

Input{"nums":[2,2,2]}

Expected[[],[2],[2,2],[2,2,2]]

⏱ Performance - must finish in 2000ms

All elements duplicates; subsets include empty and incremental duplicates.

💡 Sorting groups duplicates together.

💡 Skip duplicates at the same recursion level to avoid repeated subsets.

💡 Backtracking with skip condition on duplicates is essential here.

Why it failed: Duplicates in output or missing subsets due to not skipping duplicates properly. Fix by skipping nums[i] if nums[i] == nums[i-1] and i > start index.

✓ Correct subsets generated with duplicates handled properly.

t2_04edge

Input{"nums":[1,1,1,1,1]}

Expected[[],[1],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1]]

⏱ Performance - must finish in 2000ms

All elements identical; subsets include empty and incremental duplicates.

💡 Sorting groups duplicates together.

💡 Skip duplicates at the same recursion level to avoid repeated subsets.

💡 Backtracking with skip condition on duplicates is essential here.

Why it failed: Duplicates in output or missing subsets due to not skipping duplicates properly. Fix by skipping nums[i] if nums[i] == nums[i-1] and i > start index.

✓ Correct subsets generated with all identical elements.

t3_01corner

Input{"nums":[1,2,2,2]}

Expected[[],[1],[1,2],[1,2,2],[1,2,2,2],[2],[2,2],[2,2,2]]

⏱ Performance - must finish in 2000ms

Tests correct skipping of multiple duplicates at same recursion level.

💡 Check how multiple duplicates are handled in recursion.

💡 Skip duplicates only when they appear consecutively at the same recursion depth.

💡 Use condition: if i > start and nums[i] == nums[i-1], continue to next iteration.

Why it failed: Incorrect subsets due to skipping duplicates incorrectly or not skipping enough. Fix by applying skip condition only at same recursion level.

✓ Correctly handles multiple duplicates with proper skipping.

t3_02corner

Input{"nums":[1,1,2,2]}

Expected[[],[1],[1,1],[1,1,2],[1,1,2,2],[1,2],[1,2,2],[2],[2,2]]

⏱ Performance - must finish in 2000ms

Tests handling of two different duplicates groups.

💡 Sort input to group duplicates.

💡 Skip duplicates at same recursion level for both duplicate groups.

💡 Backtracking with skip condition applies to each duplicate group separately.

Why it failed: Duplicates or missing subsets due to incorrect skip logic across multiple duplicate groups. Fix by applying skip condition for each group at same recursion level.

✓ Correct subsets generated with multiple duplicate groups handled.

t3_03corner

Input{"nums":[1,2,2,3]}

Expected[[],[1],[1,2],[1,2,2],[1,2,2,3],[1,2,3],[1,3],[2],[2,2],[2,2,3],[2,3],[3]]

⏱ Performance - must finish in 2000ms

Greedy trap test: ensure no subsets skipped incorrectly by greedy approach.

💡 Do not greedily skip subsets; explore all include/exclude paths.

💡 Use backtracking with skip only for duplicates at same recursion level.

💡 Check that subsets with and without duplicates are both included.

Why it failed: Missing subsets due to greedy skipping of some branches. Fix by exploring both include and exclude branches and skipping duplicates only at same recursion level.

✓ All valid subsets generated without greedy skipping.

t4_01performance

Input{"nums":[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50,50]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100 with many duplicates; O(2^n) brute force will time out.

💡 Backtracking with pruning and skipping duplicates is essential.

💡 Sorting input and skipping duplicates at same recursion level reduces redundant work.

💡 DP or iterative approaches won't help due to exponential subsets count.

Why it failed: TLE due to exponential complexity O(2^n). Fix by pruning duplicates with skip condition and efficient backtracking.

✓ Algorithm runs within time limit confirming O(2^n) complexity handled with pruning.

Practice

1. You need to find all unique combinations of exactly k distinct numbers from 1 to 9 that add up to a target sum n. Which algorithmic approach guarantees finding all valid combinations efficiently by exploring partial solutions and pruning impossible paths early?

easy

A. Greedy algorithm that picks the largest numbers first until the sum is reached or exceeded

B. Backtracking with pruning based on current sum and remaining numbers' possible sums

C. Dynamic programming that counts combinations without generating them explicitly

D. Sorting the numbers and using two pointers to find pairs that sum to n

Solution

1. Step 1: Understand problem constraints

   The problem requires all unique combinations of size k from numbers 1 to 9 summing to n, which suggests exploring subsets.

2. Step 2: Identify suitable algorithm

   Backtracking with pruning efficiently explores partial combinations and stops early when sums cannot reach n, guaranteeing correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning is standard for combination sum problems [OK]

Hint: Backtracking with pruning finds all valid combos efficiently [OK]

Common Mistakes:

• Thinking greedy or two pointers can find all combinations
• Confusing counting with generating combinations

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

3. The following code attempts to find the largest divisible subset but contains a subtle bug. Identify the line with the bug.

def largestDivisibleSubset(nums):
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[j] % nums[i] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

medium

A. Line with 'result.append(nums[max_index])'

B. Line with 'dp = [1] * n'

C. Line with 'max_index = 0'

D. Line with 'if nums[j] % nums[i] == 0:'

Solution

1. Step 1: Check divisibility condition

   The condition should be nums[i] % nums[j] == 0 because we want to check if current number is divisible by a smaller number.

2. Step 2: Understand impact of bug

   Using nums[j] % nums[i] == 0 reverses the divisibility logic, causing incorrect dp updates and wrong subsets.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct divisibility check is crucial for correctness [OK]

Hint: Divisibility check direction matters [OK]

Common Mistakes:

• Swapping divisor and dividend in modulo check
• Not sorting input before DP
• Incorrect subset reconstruction

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

5. Suppose the problem is modified so that puzzles can have repeated letters and words can be counted multiple times if they match multiple subsets of the puzzle letters. Which modification to the optimal bitmask + trie approach correctly handles this variant?

hard

A. Preprocess puzzles to remove duplicates and apply the original algorithm unchanged.

B. Modify dfs to not require the puzzle's first letter to be present in the word and allow counting multiple matches per word.

C. Enumerate all subsets of puzzle letters including duplicates and sum counts from trie traversal without filtering first letter.

D. Use a multiset trie that stores counts for repeated letters and traverse all subsets including duplicates.

Solution

1. Step 1: Understand variant requirements

   Repeated letters in puzzles and multiple counting per word require handling multisets, not just sets.

2. Step 2: Modify data structure and traversal

   A multiset trie that stores counts for repeated letters and traverses all subsets including duplicates correctly counts all matches.

3. Step 3: Why other options fail

   Ignoring first letter breaks mandatory condition; removing duplicates loses information; naive enumeration is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Multiset trie handles repeated letters and multiple counts correctly [OK]

Hint: Multiset trie needed for repeated letters and multiple counts [OK]

Common Mistakes:

• Ignoring repeated letters
• Removing duplicates incorrectly
• Dropping first letter condition