Subsets II (With Duplicates)

🎯

Subsets II (With Duplicates)

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you have a collection of colored beads, some colors repeating, and you want to find all unique ways to select any number of beads without caring about order.

💡 This problem is about generating all unique subsets from a list that may contain duplicates. Beginners often struggle because duplicates cause repeated subsets, and handling them requires careful logic to avoid redundant results.

📋

Problem Statement

Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets. The solution set must not contain duplicate subsets. Return the solution in any order.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4

💡

Example

Input"[1,2,2]"

Output[[],[1],[1,2],[1,2,2],[2],[2,2]]

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.

• Empty input array → output [[]]
• All elements are duplicates, e.g. [2,2,2] → output [[],[2],[2,2],[2,2,2]]
• Array with no duplicates, e.g. [1,2,3] → output all 8 subsets
• Large input with many duplicates → ensure no timeout and no duplicates in output

⚠️

Common Mistakes

Not sorting input before recursion

Duplicates are not adjacent, so skipping duplicates fails, causing repeated subsets.

✅ Always sort input before backtracking to group duplicates.

Skipping duplicates incorrectly (e.g., skipping all duplicates, not just at same recursion level)

Some valid subsets are missed or duplicates remain.

✅ Only skip duplicates when the current index is greater than the start index in the loop.

Modifying the path list without backtracking (not popping after recursion)

Path accumulates extra elements, causing wrong subsets.

✅ Always pop the last element after recursive call to restore state.

Using a set of lists without converting to tuples (in Python)

Runtime error because lists are unhashable.

✅ Convert lists to tuples before adding to set.

🧠

Brute Force (Pure Recursion with Deduplication by Set)

💡 This approach introduces the basic idea of generating all subsets by recursion but uses a set to remove duplicates after generation. It is simple but inefficient and helps understand the problem's nature.

Intuition

Generate all subsets by including or excluding each element recursively. Because duplicates exist, store subsets in a set to avoid duplicates.

Algorithm

1. Sort the input array to group duplicates together.
2. Use recursion to explore two choices at each index: include or exclude the current element.
3. At each recursion leaf, add the current subset to a set to avoid duplicates.
4. Convert the set to a list and return all unique subsets.

💡 The main challenge is duplicates causing repeated subsets; sorting and using a set after generation is a straightforward but costly way to handle this.

</>

Code

from typing import List

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = set()
    def backtrack(i, path):
        if i == len(nums):
            res.add(tuple(path))
            return
        # Exclude nums[i]
        backtrack(i + 1, path)
        # Include nums[i]
        backtrack(i + 1, path + [nums[i]])
    backtrack(0, [])
    return [list(t) for t in res]

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

Line Notes

nums.sort()Sort to group duplicates, making it easier to handle them later.

res = set()Use a set to automatically remove duplicate subsets.

if i == len(nums):Base case: when index reaches end, add current subset to results.

res.add(tuple(path))Convert list to tuple to store in set because lists are unhashable.

import java.util.*;

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> res = new HashSet<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return new ArrayList<>(res);
    }
    private void backtrack(int[] nums, int index, List<Integer> path, Set<List<Integer>> res) {
        if (index == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // Exclude nums[index]
        backtrack(nums, index + 1, path, res);
        // Include nums[index]
        path.add(nums[index]);
        backtrack(nums, index + 1, path, res);
        path.remove(path.size() - 1);
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsetsWithDup(new int[]{1,2,2}));
    }
}

Line Notes

Arrays.sort(nums);Sort input to group duplicates for easier handling.

Set<List<Integer>> res = new HashSet<>();Use a set to avoid duplicate subsets.

if (index == nums.length)Base case: add current subset to results when end reached.

res.add(new ArrayList<>(path));Add a copy of current subset to results to avoid mutation.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        set<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return vector<vector<int>>(res.begin(), res.end());
    }
private:
    void backtrack(vector<int>& nums, int index, vector<int>& path, set<vector<int>>& res) {
        if (index == nums.size()) {
            res.insert(path);
            return;
        }
        // Exclude nums[index]
        backtrack(nums, index + 1, path, res);
        // Include nums[index]
        path.push_back(nums[index]);
        backtrack(nums, index + 1, path, res);
        path.pop_back();
    }
};

// Driver code
int main() {
    Solution sol;
    vector<int> nums = {1,2,2};
    vector<vector<int>> result = sol.subsetsWithDup(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            cout << subset[i];
            if (i < subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort input to group duplicates for easier handling.

set<vector<int>> res;Use a set to automatically remove duplicate subsets.

if (index == nums.size()) {Base case: add current subset to results when end reached.

res.insert(path);Insert current subset into set to avoid duplicates.

function subsetsWithDup(nums) {
    nums.sort((a,b) => a - b);
    const res = new Set();
    function backtrack(i, path) {
        if (i === nums.length) {
            res.add(path.join(','));
            return;
        }
        // Exclude nums[i]
        backtrack(i + 1, path);
        // Include nums[i]
        backtrack(i + 1, path.concat(nums[i]));
    }
    backtrack(0, []);
    return Array.from(res).map(s => s === '' ? [] : s.split(',').map(Number));
}

// Driver code
console.log(subsetsWithDup([1,2,2]));

Line Notes

nums.sort((a,b) => a - b);Sort input to group duplicates for easier handling.

const res = new Set();Use a set to remove duplicate subsets by storing string keys.

if (i === nums.length) {Base case: add current subset to results when end reached.

res.add(path.join(','));Convert subset to string to store in set since arrays are unhashable.

⏱

Complexity

TimeO(2^n * n) due to generating all subsets and converting to tuples/lists

SpaceO(2^n * n) for storing all subsets in the set

We explore all subsets (2^n). Each subset can be up to length n, and storing in a set requires hashing/conversion.

💡 For n=20, this means over a million subsets, which is very slow and memory-heavy.

Interview Verdict: Accepted but inefficient; not suitable for large inputs

This approach works but is too slow for large inputs. It is useful to understand the problem and correctness before optimizing.

🧠

Backtracking with Sorting and Skip Duplicates at Same Recursion Level

💡 This approach improves efficiency by sorting and skipping duplicates during recursion, avoiding generating duplicate subsets in the first place.

Intuition

Sort the array so duplicates are adjacent. When choosing elements at the same recursion depth, skip duplicates to prevent repeated subsets.

Algorithm

1. Sort the input array to group duplicates.
2. Use backtracking to explore subsets starting from an index.
3. At each recursion level, iterate over candidates starting from current index.
4. Skip elements that are the same as the previous one at the same recursion level to avoid duplicates.
5. Add the current path to results at each recursion call.

💡 Skipping duplicates at the same recursion level is the key insight to avoid repeated subsets without extra memory.

</>

Code

from typing import List

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

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

Line Notes

nums.sort()Sort to group duplicates for easy skipping.

res.append(path[:])Add current subset copy to results at each recursion call.

if i > start and nums[i] == nums[i-1]:Skip duplicates at the same recursion level to avoid repeated subsets.

path.pop()Backtrack by removing last element to explore other subsets.

import java.util.*;

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsetsWithDup(new int[]{1,2,2}));
    }
}

Line Notes

Arrays.sort(nums);Sort input to group duplicates for easy skipping.

res.add(new ArrayList<>(path));Add a copy of current subset to results at each recursion call.

if (i > start && nums[i] == nums[i - 1]) continue;Skip duplicates at the same recursion level to avoid repeated subsets.

path.remove(path.size() - 1);Backtrack by removing last element to explore other subsets.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return res;
    }
private:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path);
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.pop_back();
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<int> nums = {1,2,2};
    vector<vector<int>> result = sol.subsetsWithDup(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            cout << subset[i];
            if (i < subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort input to group duplicates for easy skipping.

res.push_back(path);Add current subset to results at each recursion call.

if (i > start && nums[i] == nums[i - 1]) continue;Skip duplicates at the same recursion level to avoid repeated subsets.

path.pop_back();Backtrack by removing last element to explore other subsets.

function subsetsWithDup(nums) {
    nums.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path) {
        res.push([...path]);
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue;
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    backtrack(0, []);
    return res;
}

// Driver code
console.log(subsetsWithDup([1,2,2]));

Line Notes

nums.sort((a,b) => a - b);Sort input to group duplicates for easy skipping.

res.push([...path]);Add a copy of current subset to results at each recursion call.

if (i > start && nums[i] === nums[i - 1]) continue;Skip duplicates at the same recursion level to avoid repeated subsets.

path.pop();Backtrack by removing last element to explore other subsets.

⏱

Complexity

TimeO(2^n * n) due to generating all subsets and copying them

SpaceO(2^n * n) for storing all subsets

We generate all subsets but skip duplicates early, reducing redundant work. Each subset copy costs O(n).

💡 For n=20, this is still large but much faster than brute force with set deduplication.

Interview Verdict: Accepted and efficient for typical interview constraints

This is the standard approach to solve this problem efficiently and is expected in interviews.

🧠

Iterative Approach with Sorting and Skipping Duplicates

💡 This approach uses iteration instead of recursion to build subsets step-by-step, carefully skipping duplicates to avoid repeated subsets.

Intuition

Start with an empty subset. For each number, add it to existing subsets to form new subsets. When duplicates appear, only add to subsets created in the previous step to avoid duplicates.

Algorithm

1. Sort the input array to group duplicates.
2. Initialize result with an empty subset.
3. Iterate over each number in nums.
4. If current number is a duplicate, only extend subsets created in the previous iteration.
5. Otherwise, extend all existing subsets with the current number.
6. Return the result containing all unique subsets.

💡 Tracking the start index for new subsets when duplicates appear is the key to avoid duplicates without recursion.

</>

Code

from typing import List

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = [[]]
    start = 0
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            s = start
        else:
            s = 0
        start = len(res)
        for j in range(s, len(res)):
            res.append(res[j] + [nums[i]])
    return res

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

Line Notes

nums.sort()Sort to group duplicates for easy handling.

res = [[]]Start with empty subset in results.

if i > 0 and nums[i] == nums[i - 1]:Detect duplicates to limit extension to new subsets only.

res.append(res[j] + [nums[i]])Create new subsets by adding current number to existing subsets.

import java.util.*;

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            int s = 0;
            if (i > 0 && nums[i] == nums[i - 1]) {
                s = start;
            }
            start = res.size();
            int size = res.size();
            for (int j = s; j < size; j++) {
                List<Integer> subset = new ArrayList<>(res.get(j));
                subset.add(nums[i]);
                res.add(subset);
            }
        }
        return res;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsetsWithDup(new int[]{1,2,2}));
    }
}

Line Notes

Arrays.sort(nums);Sort to group duplicates for easy handling.

res.add(new ArrayList<>());Initialize results with empty subset.

if (i > 0 && nums[i] == nums[i - 1]) {Detect duplicates to limit extension to new subsets only.

res.add(subset);Add new subset formed by adding current number.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res = {{} };
        int start = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int s = 0;
            if (i > 0 && nums[i] == nums[i - 1]) {
                s = start;
            }
            start = res.size();
            int size = res.size();
            for (int j = s; j < size; ++j) {
                vector<int> subset = res[j];
                subset.push_back(nums[i]);
                res.push_back(subset);
            }
        }
        return res;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<int> nums = {1,2,2};
    vector<vector<int>> result = sol.subsetsWithDup(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            cout << subset[i];
            if (i < subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort to group duplicates for easy handling.

vector<vector<int>> res = {{}};Initialize results with empty subset.

if (i > 0 && nums[i] == nums[i - 1]) {Detect duplicates to limit extension to new subsets only.

res.push_back(subset);Add new subset formed by adding current number.

function subsetsWithDup(nums) {
    nums.sort((a,b) => a - b);
    const res = [[]];
    let start = 0;
    for (let i = 0; i < nums.length; i++) {
        let s = 0;
        if (i > 0 && nums[i] === nums[i - 1]) {
            s = start;
        }
        start = res.length;
        const size = res.length;
        for (let j = s; j < size; j++) {
            res.push(res[j].concat(nums[i]));
        }
    }
    return res;
}

// Driver code
console.log(subsetsWithDup([1,2,2]));

Line Notes

nums.sort((a,b) => a - b);Sort to group duplicates for easy handling.

const res = [[]];Initialize results with empty subset.

if (i > 0 && nums[i] === nums[i - 1]) {Detect duplicates to limit extension to new subsets only.

res.push(res[j].concat(nums[i]));Add new subset formed by adding current number.

⏱

Complexity

TimeO(2^n * n) due to generating all subsets and copying them

SpaceO(2^n * n) for storing all subsets

We build subsets iteratively, skipping duplicates by limiting extension to new subsets only, reducing redundant work.

💡 For n=20, this approach is efficient and avoids recursion stack overhead.

Interview Verdict: Accepted and efficient; good alternative to recursion

This iterative approach is a neat alternative to recursion and is often appreciated in interviews for its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (backtracking with skip duplicates) is the best to code in interviews for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursion + Set Deduplication)	O(2^n * n)	O(2^n * n)	Yes (deep recursion)	Yes	Mention only - never code due to inefficiency
2. Backtracking with Sorting and Skip Duplicates	O(2^n * n)	O(2^n * n)	Yes (deep recursion)	Yes	Code this approach in 95% of interviews
3. Iterative with Sorting and Skip Duplicates	O(2^n * n)	O(2^n * n)	No	Yes	Good alternative if recursion is not preferred

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and ask about duplicates and output format.Step 2: Present the brute force recursive approach with set deduplication to show understanding.Step 3: Improve to backtracking with sorting and skipping duplicates at the same recursion level.Step 4: Optionally present the iterative approach as an alternative.Step 5: Write clean code and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of backtracking, handling duplicates, optimization, and clean coding.

Common Follow-ups

• What if input is very large? → Use iterative or pruning to optimize memory.
• Can you generate subsets of fixed size k? → Modify recursion to track subset size.

💡 Follow-ups test your ability to adapt the solution to constraints and variations.

🔍

Pattern Recognition

When to Use

1) Asked to generate all subsets or combinations 2) Input may contain duplicates 3) Need unique subsets 4) Order of subsets does not matter

Signature Phrases

return all possible subsetsthe solution set must not contain duplicate subsets

NOT This Pattern When

Problems asking for permutations without duplicates or subsets with fixed size k only

Similar Problems

Subsets I (No Duplicates) - simpler version without duplicatesCombination Sum II - similar duplicate handling in combinationsPermutations II - duplicate handling in permutations

Practice

1. Consider the following Python code implementing the optimal backtracking solution for Combination Sum II. What is the final returned list when calling combinationSum2([1,2,2], 4)?

easy

A. [[1,2,2]]

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

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

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

Solution

1. Step 1: Sort candidates and start backtracking

   Sorted candidates: [1,2,2]. Start from index 0 with target=4.

2. Step 2: Explore combinations skipping duplicates at same level

   Try 1 -> target=3, then try 2 at next index -> target=1, next 2 is duplicate at same level skipped. No further candidates fit. Backtrack and try 2 at index 1 -> target=2, next 2 at index 2 -> target=0, add [2,2]. Both [1,2,2] and [2,2] are valid unique combinations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both [1,2,2] and [2,2] sum to 4 without reuse and duplicates skipped [OK]

Hint: Duplicate skipping prevents repeated combinations [OK]

Common Mistakes:

• Including partial sums like [2]
• Allowing reuse of elements
• Not skipping duplicates at same recursion level

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

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

4. You need to generate all possible subsets of a given set of distinct integers. Which algorithmic approach guarantees enumerating every subset exactly once, including the empty subset, without missing or duplicating any subset?

easy

A. Greedy algorithm that picks elements based on a heuristic to maximize subset size

B. Dynamic programming approach that builds subsets by summing elements to target values

C. Backtracking with include/exclude decisions at each element to explore all subset combinations

D. Sorting the array and then using two pointers to find pairs that form subsets

Solution

1. Step 1: Understand problem requirements

   The problem requires enumerating all subsets, which means exploring all combinations of including or excluding each element.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude decisions systematically explores all subsets without duplication or omission, including the empty subset.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking ensures all subsets are generated [OK]

Hint: Include/exclude backtracking covers all subsets [OK]

Common Mistakes:

• Confusing subset generation with greedy or DP sum problems

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