Problem overview
The method subsetsWithDup receives nums, an array of integers that may contain repeats, and returns every distinct subset: every way to pick some of the numbers, from none (the empty subset) to all of them. Two subsets are the same when they hold the same values the same number of times, whichever copies they use. In [1, 2, 2], picking the first 2 or the second 2 gives the same subset [2], which must appear once.
The numbers of each subset are written in ascending order, and the subsets come in lexicographic order: compare two subsets number by number, the first difference decides, and a subset that is the beginning of another comes first. The empty subset is always first. For [1, 2, 2] the answer is [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. For [4, 4, 4, 1, 4], sorted as [1, 4, 4, 4, 4], a subset is fixed by whether it has the 1 and how many 4s it has, from 0 to 4, so there are 2 × 5 = 10 of them.
The array has between 1 and 10 numbers, each between -10 and 10.
Approach: choose the next number, and never try the same value twice
There are two natural ways to enumerate subsets. One decides, for each number in turn, whether to take it or skip it. The other, used here, builds the subset by choosing its next number: a call gets start, the first index it may still use, and current, the subset built so far. It saves a copy of current first, because every subset the search builds is an answer, not only the full ones. Then a loop tries each index i from start on as the next number: add nums[i], call itself with i + 1, and remove the number again. Starting at start and moving forward keeps each subset in index order, so in ascending order after the sort.
Duplicates are the difficulty. With [1, 2, 2], a loop that tries every index would pick index 1 and index 2 as the next number after [1], and both lead to the same subsets, [1, 2] and [1, 2, 2], twice over. Sorting puts equal values side by side, so the fix is one line: inside a loop, skip nums[i] when i > start and it equals nums[i - 1]. That value has already been tried as the next number in this call.
The condition says i > start, not i > 0, and the difference matters. At i = start the number is the first one this call tries, so it is taken even if it equals its left neighbour. That is how [2, 2] gets its second 2: the call that already holds one 2 starts at the second 2's index and takes it. With i > 0, the second 2 would never be taken and [1, 2, 2] would give only [[], [1], [1, 2], [2]].
Because the loop form considers each value once per position, the subsets come out already in the order the statement asks for. There are at most 2^n subsets and copying one takes up to n steps.
Step by step
- Sort
numsin place withsort((a, b) => a - b). With no comparison function,sortcompares numbers as text, and[10, 2, 2]stays as it is because"10"comes before"2". The sort also makes equal values neighbours and fixes the output order. - Create
resultas an emptynumber[][]. - Start the search with
this.backtrack(nums, 0, [], result): nothing chosen, every index available. - Return
result, which the search filled in place. - Write the helper
backtrack(nums, start, current, result)inside the class, returningvoid. - Save a copy of
currentwith[...current]as the first line. The arraycurrentkeeps changing as the search runs, so the result needs a snapshot. - Loop with
let i = startwhilei < nums.length. Whenstartis past the last index, the loop does not run, and that is where the search ends. - Skip repeats: if
i > startandnums[i] === nums[i - 1],continue. - Take the number: push
nums[i]ontocurrent. - Recurse with
i + 1, so each number is used at most once and the subset stays ascending. - Undo the choice with
current.pop(), so the loop can try the next number in its place.
The solution in TypeScript
class Solution {
subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const result: number[][] = [];
this.backtrack(nums, 0, [], result);
return result;
}
backtrack(nums: number[], start: number, current: number[], result: number[][]): void {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
current.push(nums[i]);
this.backtrack(nums, i + 1, current, result);
current.pop();
}
}
}
TypeScript details worth knowing:
[...current]copies. The spread creates a new array with the same numbers. Arrays are objects, soresult.push(current)would store a reference to the one array that the search keeps changing. After the search, every entry would be that same array, and since it ends empty, the result for[1, 2, 2]would be six empty arrays:[[], [], [], [], [], []].sortchanges the input. It sortsnumsin place, so the caller's array is reordered too. A call with[2, 1, 2]leaves that array as[1, 2, 2].- Types are erased.
number[][]andvoidexist only for the compiler. The JavaScript that runs has no types. - Shared
current. The same array is passed down every call, which is why thepop()after each recursive call is needed: it restores the array for the next turn of the loop.
Complexity
Time: O(n · 2^n). There are at most 2^n subsets, and copying one costs up to n steps. The sort adds O(n log n), which is smaller. For ten distinct numbers the result has 1024 subsets; for ten equal numbers it has only 11, because the skip rule prunes the repeats before any work is done on them.
Space: O(n) besides the answer. The subset being built holds at most n numbers, and the recursion is at most n calls deep.
Edge cases and common mistakes
- Forgetting to sort. Equal values must be neighbours for the skip rule to work. Without the sort,
[2, 1, 2]returns[[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]:[2]appears twice and the subsets are not ascending. - Using
i > 0instead ofi > start. It drops valid subsets, as shown above:[1, 2, 2]loses[1, 2, 2]and[2, 2]. - Saving
currentwithout copying. It stores one array again and again, as explained above. - Sorting without a comparison. It sorts as text.
- Single element.
[0]gives[[], [0]]. The empty subset is always in the answer, and it is the first one. - All equal. Ten 3s give 11 subsets: none, one, two, and so on up to ten.
- Negative numbers.
[-1, -1, 3]gives[[], [-1], [-1, -1], [-1, -1, 3], [-1, 3], [3]]. The numeric comparison puts -1 before 3.
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[]and[1]to[4, 4, 4, 4].[10, 2, 2]gives[[], [2], [2, 2], [2, 2, 10], [2, 10], [10]].[-1, -1, 3]gives the six subsets listed above.- Ten different numbers give 1024 subsets.
