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. Consider the following Python code implementing the optimal backtracking solution for Combination Sum III. What is the final value of res after calling combinationSum3(3, 7)?

easy

A. [[1, 2, 4]]

B. [[1, 3, 3]]

C. [[2, 2, 3]]

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls for k=3, n=7

   Start from 1, try combinations of size 3 summing to 7. Valid combos are [1,2,4] only because 1+2+4=7.

2. Step 2: Verify no other combos meet criteria

   Other combos like [1,3,3] or [2,2,3] are invalid due to duplicates or sum mismatch.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only [1,2,4] sums to 7 with 3 distinct numbers [OK]

Hint: Only distinct numbers summing to 7 with size 3 is [1,2,4] [OK]

Common Mistakes:

• Including duplicates like [1,3,3]
• Miscounting sum or size

2. Consider the following code snippet for counting max bitwise-OR subsets. What is the returned value when input is [1, 2, 3]?

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(1, 1 << n):
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

sol = Solution()
print(sol.countMaxOrSubsets([1, 2, 3]))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Enumerate all non-empty subsets and their OR

   Subsets: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} with ORs 1, 2, 3, 3, 3, 3, 3 respectively.

2. Step 2: Identify max OR and count subsets with that OR

   Max OR is 3; subsets with OR=3 are {3}, {1,2}, {1,3}, {2,3}, {1,2,3} -> 5 subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counted 5 subsets with max OR 3 -> matches 5 [OK]

Hint: Count subsets with OR equal to max OR -> 5 [OK]

Common Mistakes:

• Counting empty subset as valid
• Miscounting subsets with max OR

3. Identify the bug in the following code snippet that generates subsets iteratively:

medium

A. Modifying subsets in place without copying causes all subsets to be identical

B. Extending result inside the loop causes infinite loop

C. Starting result with [[]] misses the empty subset

D. Using append instead of extend on subsets is incorrect

Solution

1. Step 1: Analyze subset modification

   The code appends num directly to subsets in result, modifying them in place.

2. Step 2: Consequence of in-place modification

   All subsets in result end up referencing the same list, causing duplicates and incorrect subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach copies subsets before adding new elements [OK]

Hint: Always copy subsets before adding new elements [OK]

Common Mistakes:

• Modifying lists in place
• Extending result inside loop without fix
• Wrong initial result value

4. Suppose the problem is modified so that numbers 1 to 9 can be reused any number of times in combinations summing to n with size k. Which change to the backtracking algorithm correctly handles this variant?

hard

A. Add a visited set to prevent reusing numbers and keep backtrack(i + 1, comb, total + i)

B. Keep the recursive call as backtrack(i + 1, comb, total + i) but allow duplicates in the result

C. Change the recursive call to backtrack(i, comb, total + i) to allow reuse of the same number i

D. Use a dynamic programming approach instead of backtracking to handle reuse efficiently

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means the same number can be chosen multiple times, so next recursion should start at current number i, not i+1.

2. Step 2: Modify recursive call

   Change backtrack(i + 1, ...) to backtrack(i, ...) to allow repeated picks of i.

3. Step 3: Confirm correctness

   This change correctly explores combinations with repeated numbers without duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Recursing with start=i enables reuse of number i [OK]

Hint: Reuse requires recursive calls with start index unchanged [OK]

Common Mistakes:

• Not changing start index to allow reuse
• Allowing duplicates by mistake
• Switching to DP unnecessarily

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