Problem overview
The method subsetsWithDup receives a vector<int> named nums, which may contain repeated numbers, and returns every distinct subset as a vector<vector<int>>. A subset is any selection of the numbers, from none (the empty subset) to all of them. Two subsets are the same when they hold the same numbers the same number of times, whichever copies of a repeated number they use. In [1,2,2], taking the first 2 or the second 2 gives the same subset [2], which must appear once.
The answer has a fixed order. Each subset is written in ascending order, and the subsets are in lexicographic order: the first position where two subsets differ decides, and when one is the beginning of the other, the shorter comes first. For [1,2,2] the result is [[],[1],[1,2],[1,2,2],[2],[2,2]]. For [4,4,4,1,4], which sorts to [1,4,4,4,4], a subset is fixed by whether it has the 1 and how many 4s it has (0 to 4), so there are 2 × 5 = 10 subsets.
Approach: build subsets by choosing the next number
Sort first. Equal numbers then sit next to each other, which makes a repeat easy to spot, and the sorted order gives each subset its ascending order.
The search works like this. A call receives start, the first index it may still use, and current, the subset built so far. Every subset the search builds is an answer, so the call saves a copy of current right away. Then a loop chooses the next number of the subset: for each index i from start on, it adds nums[i], calls itself with i + 1 to grow the subset further, and removes the number again so the loop can try the following one. Starting at start and never going back keeps every subset in index order, and so in ascending order, and uses each position at most once.
Without more care, repeated numbers produce repeated subsets. For [1,2,2] the loop at the top level would pick the first 2, then the second 2, and both would grow into [2]. The fix is one condition: inside a call, skip nums[i] when i > start and it equals nums[i - 1]. Every turn of the loop picks a different next number, and taking another copy of a value the loop already tried would rebuild the same subsets. A copy is still taken when it is the first one this call tries, at i == start, and that is how [2,2] gets its second 2.
The order comes out right without extra work. The search saves a subset before extending it, so a subset appears before every longer subset that starts with it. The loop tries smaller numbers first, so the subsets that start with a smaller number come first.
Step by step
- Sort
numswithsort(nums.begin(), nums.end()). - Create
result, avector<vector<int>>for the subsets found. - Create
current, an emptyvector<int>: the subset being built. - Start the search at index 0 with the empty subset.
- Return
resultafter the call. The helper added to that same vector. - Declare the helper.
backtrackreturnsvoidand takesnums,start,currentandresult. The vectors are passed by reference because the helper changescurrentandresult, and the caller must see it. - Save the subset. The first line pushes
currentintoresult, with no condition: [], [1] and [1,2] are all answers. - Loop with
ifromstartto the end ofnums. Whenstartis past the last index, the loop doesn't run and the search stops there. - Skip repeats. If
i > startandnums[i] == nums[i - 1],continue. - Take the number with
current.push_back(nums[i]). - Recurse with
i + 1as the newstart. - Undo with
current.pop_back(), socurrentis what it was before this turn.
The solution in C++
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
vector<int> current;
backtrack(nums, 0, current, result);
return result;
}
void backtrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
result.push_back(current);
for (int i = start; i < nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
current.push_back(nums[i]);
backtrack(nums, i + 1, current, result);
current.pop_back();
}
}
};
The C++ details worth a closer look:
push_backcopies.result.push_back(current)stores a copy of the vector as it is at that moment. That is whycurrentcan keep changing afterwards without touching the saved subsets.- The same
currentis shared by every call. It is passed by reference, so a single vector is built up and torn down during the whole search. This is why eachpush_backneeds its matchingpop_back. numsis sorted in place. The parameter is a non-const reference, so after the call the caller's vector is sorted too: calling the method on{2,1,2}leaves it as{1,2,2}.- Signed and unsigned.
nums.size()is unsigned andiis anint. The loop is fine for lengths up to 10, and compilers may warn about the mixed comparison.
Complexity
Time: O(n · 2^n) for n numbers. There are at most 2^n subsets, and copying one into the result takes up to n steps. Sorting costs O(n log n), which is smaller.
Space: O(n) besides the answer. The search is at most n calls deep, and current holds at most n numbers.
Ten different numbers give the maximum of 1024 subsets. Ten equal numbers give only 11, one for each count from 0 to 10, and the duplicate rule is what keeps the search from building more.
Edge cases and common mistakes
- Comparing with
i > 0instead ofi > start. That skips a repeat even when it is the first number a call tries, and subsets like[1,2,2]and[2,2]are lost. For[1,2,2]the result is only[[],[1],[1,2],[2]]. - No skip at all. For
[1,2,2]the result has 8 entries and repeats[1,2]and[2]:[[],[1],[1,2],[1,2,2],[1,2],[2],[2,2],[2]]. - Forgetting to sort. The skip rule only works when equal numbers are adjacent. For
{2,1,2}without sorting the search returns 8 subsets, with[2]twice, and the order isn't the required one. - Forgetting
pop_back().currentwould keep growing across turns of the loop, and the subsets would contain numbers that were never chosen together. - Passing
iinstead ofi + 1. A number could then be reused within a subset. - Saving only at the end. Every partial subset is an answer, so the push into
resultgoes at the top of the function, not inside a condition. - All numbers equal.
[5,5,5]gives[[],[5],[5,5],[5,5,5]].
Testing
[1,2,2]gives[[],[1],[1,2],[1,2,2],[2],[2,2]].[0]gives[[],[0]].[4,4,4,1,4]gives 10 subsets, from[]to[4,4,4,4].[3,1,2]gives[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]].[-1,-1]gives[[],[-1],[-1,-1]].[2,1,2,2]gives[[],[1],[1,2],[1,2,2],[1,2,2,2],[2],[2,2],[2,2,2]].
