DSA interview question

Subsets II (Input Has Duplicates)

Medium · Algorithms · Topics: recursion, backtracking

The problem

A recipe app lets users choose any combination of the ingredients they have, and some ingredients appear more than once (two eggs, three tomatoes). The app wants every distinct selection: taking "one of the two eggs" is the same selection no matter which egg. With duplicates, the plain power set lists the same multiset several times. The fix mirrors Combination Sum II: sort, build subsets by choosing the next element from start onward, and at each level try each distinct value only once. Every node of this recursion tree is a distinct subset.

Example: [1, 2, 2] → [] [1] [1,2] [1,2,2] [2] [2,2].

Function signature

vector<vector<int>> subsetsWithDup(vector<int> nums);  // lexicographic order

Test cases

Input	Output	Explanation
`[1, 2, 2]`	`[] [1] [1,2] [1,2,2] [2] [2,2]`	6 distinct subsets, not 8
`[0]`	`[] [0]`
`[4, 4, 4, 1, 4]`	`[] [1] [1,4] [1,4,4] [1,4,4,4] [1,4,4,4,4] [4] [4,4] [4,4,4] [4,4,4,4]`	2 · 5 = 10
`[3, 1]`	`[] [1] [1,3] [3]`	No duplicates, so the plain power set
`[]`	`[]`

(Confirm: subsets are compared as multisets; each subset is output once; any order is acceptable, and sorted order is shown here.)

How interviewers phrase it

"Given an integer array that may contain duplicates, return all possible subsets without duplicate subsets" (LeetCode 90).

Clarifying questions to ask

Is [1,2] the same as [2,1]? (Yes, multisets.)
Does the output order matter?
How large is n? (Up to about 10, so the output is at most 2¹⁰.)

Follow-ups to expect

"Why record at every node, not just the leaves?"
"Why does the skip rule work?"
"How many distinct subsets are there?"
"Could you use a set instead?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview