Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Google SWE coding round with a subsets problem that looks easy until duplicates show up and you realize your initial approach generates repeats everywhere.

Questions Asked (1)

Given an integer array that may contain duplicates, return all possible subsets without any duplicate subsets in the result.

Algorithms & Data Structures

Author's notes

My first instinct was the standard backtracking approach I'd used for the no-duplicates version, and it immediately produced duplicate subsets.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the array to group duplicates, then use backtracking to generate subsets while skipping duplicate elements at each decision level. Alternatively, use an iterative approach that builds subsets and avoids duplicates by only adding new elements that are different from the previous one when extending subsets of the same size.

Pro tip: Clarify whether the input array can be modified (sorting in-place) and discuss the trade-offs between sorting and using a hash set for deduplication. Also, mention that the output order doesn't matter, so you can choose the most efficient method.

1. Understand the problem and constraints

Confirm that the input may contain duplicates and that the output should not contain duplicate subsets. Discuss potential constraints like array size and value range.

2. Choose an approach

Decide between backtracking with sorting or an iterative approach. Explain why sorting helps in skipping duplicates efficiently.

3. Implement the algorithm

Write code for the chosen approach. For backtracking, at each step, skip duplicates by checking if the current element is the same as the previous and not the first in the current level.

4. Analyze complexity

State the time complexity: O(2^n) in the worst case (when all elements are unique), but with duplicates, it's O(2^n) as well since the number of subsets is at most 2^n. Space complexity: O(n) for recursion stack and O(2^n) for output.

5. Test with examples

Walk through examples like [1,2,2] and [0] to ensure no duplicate subsets are generated and all valid subsets are included.

Key Points to Mention

Sorting the array to bring duplicates together, which allows skipping duplicates during backtracking.
The backtracking template: at each index, decide to include or exclude the current element, but skip duplicates by checking if the current element equals the previous and the previous was not included.
Alternative iterative approach: start with [[]], and for each number, if it's the same as the previous, only add it to subsets created in the previous step; otherwise, add to all existing subsets.
Time complexity: O(2^n) where n is the number of elements, as the number of subsets is at most 2^n. Space complexity: O(n) for recursion and O(2^n) for output.
Handling edge cases: empty array, all duplicates, and no duplicates.
Clarify that the output order does not matter, so we can return subsets in any order.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.