Problem overview
The method SubsetsWithDup receives an int[] named nums that may repeat values, and returns every distinct subset as a List<List<int>>: every way of keeping some of the numbers, from none (the empty subset) to all. Two subsets count as the same when they hold the same numbers the same number of times. In [1,2,2], keeping the first 2 or the second 2 gives the same subset [2], and it must appear once.
The numbers of each subset are in ascending order, and the subsets come in lexicographic order: the first position where two subsets differ decides, and a subset that is the beginning of another comes first. For [1,2,2] the result is [[],[1],[1,2],[1,2,2],[2],[2,2]]. For [4,4,4,1,4] there are 10 subsets. Sorted, the array is [1,4,4,4,4], and a subset is fixed by whether it holds the 1 (2 choices) and how many 4s it holds (0 to 4, so 5 choices).
Approach: grow a subset by choosing its next number
Every subset the search builds is an answer, so each call of the recursive helper first saves a copy of the subset it was given. After that, a loop picks the next number of the subset: for each index i from start on, add nums[i], call the helper with i + 1 so that later numbers come only from after this one, and then remove the number again. Starting at start and never at 0 keeps every subset in index order, so each choice of indexes is built once.
Duplicates need one extra rule, and sorting makes it simple. After Array.Sort, equal numbers sit side by side. Inside one call, each turn of the loop picks a different candidate for the next position, and trying a value that the previous turn already tried would rebuild exactly the same subsets. So the loop skips nums[i] when i > start and it equals nums[i - 1]. The first copy this call tries, at i == start, is always taken. That is how [2,2] gets its second 2: the deeper call starts after the first 2, and there the second 2 is at start.
Sorting also gives the required order. The search finds the empty subset first, and then the subsets starting with the smallest number, each followed by its extensions, so the results are already lexicographic.
Step by step
- Sort
numswithArray.Sort. It sorts in place in ascending order. - Create
result, a list of lists. - Start the search with
Backtrack(nums, 0, new List<int>(), result): nothing chosen yet, and every index from 0 is available. - Return
result. - Write
Backtrack. It takes the array,start, thecurrentsubset and theresult. - Save a copy of
currentat the top withnew List<int>(current). There is no condition around it, because every call's subset is an answer. - Loop
ifromstartto the end of the array. - Skip repeats: if
i > startandnums[i] == nums[i - 1],continue. - Choose
nums[i]withAdd, recurse withi + 1, and undo the choice withRemoveAt(current.Count - 1).
The solution in C#
class Solution {
public List<List<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
List<List<int>> result = new List<List<int>>();
Backtrack(nums, 0, new List<int>(), result);
return result;
}
public void Backtrack(int[] nums, int start, List<int> current, List<List<int>> result) {
result.Add(new List<int>(current));
for (int i = start; i < nums.Length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
current.Add(nums[i]);
Backtrack(nums, i + 1, current, result);
current.RemoveAt(current.Count - 1);
}
}
}
The C# details worth knowing:
- Why the copy matters.
List<int>is a reference type.result.Add(current)would store the same list object every time, and since the search keeps adding and removing numbers in it, every entry ofresultends up showing whatevercurrentholds at the end, an empty list.new List<int>(current)is a snapshot that stays as it is. Array.Sortchanges the caller's array. It sorts in place, so after the call the originalnumsis in ascending order.RemoveAt(current.Count - 1)removes the last element by index. CallingRemove(nums[i])would remove the first element equal to that value, which isn't always the last one.- Nested generics.
List<List<int>>is a list whose elements are lists ofint. The two closing angle brackets are written together without a space.
Complexity
Time: O(n * 2^n). There are at most 2^n subsets, and copying one takes up to n steps. Sorting is O(n log n) and doesn't change the bound. Duplicates only reduce the count: ten equal numbers give 11 subsets, not 1024.
Space: beyond the answer, O(n): the subset being built and one call per number in it.
Edge cases and common mistakes
- One element.
[0]gives[[],[0]]. - Unsorted input.
[2,1,2]gives the same answer as[1,2,2], because the method sorts first. Without sorting, equal numbers are not always side by side, and the skip rule can't see all repeats. - Forgetting the skip. On
[1,2,2]the result has 8 entries, with[1,2]and[2]twice. - Skipping with
i > 0instead ofi > start. The second 2 is then never taken after the first one, and[1,2,2]loses[1,2,2]and[2,2], leaving[[],[1],[1,2],[2]]. - Adding
currentwithout copying. Every entry of the result ends up the same list, the empty one. - Saving only at the end. Only full-length subsets would be saved, but the answer needs all of them.
Testing
[1,2,2]gives[[],[1],[1,2],[1,2,2],[2],[2,2]].[0]gives[[],[0]].[4,4,4,1,4]gives[[],[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,1,2]gives[[],[1],[1,2],[1,2,2],[2],[2,2]].- Ten different numbers give 1024 subsets, and ten equal numbers give 11.
