Problem overview
subsetsWithDup(nums) receives an array of integers that may repeat 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 numbers the same number of times, whichever copies they use. In [1,2,2] the subset [2] can be made from either 2, but it must be listed once.
Each subset is written in ascending order, and the subsets are returned in lexicographic order. Compare two subsets number by number, and the first difference decides. When one is the beginning of the other, the shorter one comes first, so 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] it has 10 subsets: a subset is fixed by whether it holds the 1 and by how many 4s it holds, from 0 to 4, so 2 times 5.
Approach: sort, then build subsets with a loop
With distinct numbers, a subset is a choice for each number: take it or leave it. With duplicates, that approach produces the same subset several times, because the two 2s in [1,2,2] look different to the algorithm but the same to the problem.
This lesson uses the loop form of backtracking. A call has current, the subset built so far, and start, the first index it may still use. It saves a copy of current first, since every subset the search builds is an answer, not only the full ones. Then it chooses the next number of the subset: for each index i from start on, it adds nums[i], recurses with i + 1 and removes the number again.
Sorting makes the duplicates easy to handle. Equal numbers sit side by side, so a repeat is spotted by comparing a number with the one before it. Inside one call, each turn of the loop picks a different next number, so trying a second copy of the same value would only rebuild the subsets already built from the first copy. The loop skips nums[i] when i > start and it equals nums[i - 1]. At i = start the copy is the first one this call tries, so it is taken: that is how [2,2] gets its second 2.
Sorting also writes each subset in ascending order, and it makes the search produce the subsets in exactly the order the problem asks for.
Step by step
- Sort
numsin place with the comparison(a, b) => a - b. Without a comparison,sortcompares the numbers as text. - Create
result, an empty array of subsets. - Start the search with
this.backtrack(nums, 0, [], result): any index may be used, and the subset is empty. - Return
result, which the helper has filled. - Declare the helper
backtrack(nums, start, current, result)in the class. - Save a snapshot at the top:
result.push([...current]). Every call saves its subset, with no condition around it. - Loop with
ifromstartwhilei < nums.length. Starting atstart, never at 0, keeps each subset in index order, so in ascending order. Whenstartis past the last index the loop doesn't run, and that is where the search stops. - Skip repeats: if
i > startandnums[i] === nums[i - 1], usecontinue. - Choose
nums[i]: push it ontocurrent. - Recurse with
i + 1, so each number is used at most once. - Undo the choice with
current.pop(), so the loop can try the next number in its place.
The solution in JavaScript
class Solution {
subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [];
this.backtrack(nums, 0, [], result);
return result;
}
backtrack(nums, start, current, result) {
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();
}
}
}
JavaScript details to watch:
sortneeds a comparator for numbers. With no comparator,[10, 2, 2].sort()gives[10, 2, 2], because the text"10"comes before"2". The search then sees the values out of order: with that sort, the code returns[[],[10],[10,2],[10,2,2],[2],[2,2]], which is not in ascending order inside the subsets.sortchanges the array it is given. The caller'snumsends up sorted. Here that is acceptable, since the function only returns the subsets.- The copy matters.
[...current]creates a new array. Pushingcurrentitself would store the same array again and again, and since it is emptied by the end of the search, every entry would be empty: the result for[1,2,2]would be eight empty arrays. continueends the current turn of the loop and moves on to the nexti, andcurrent.pop()removes the last element of the array.
Trace on [1,2,2]
Printing start and current at the start of each call lists the subsets as they are saved:
start=0 current=[]
start=1 current=[1]
start=2 current=[1,2]
start=3 current=[1,2,2]
start=2 current=[2]
start=3 current=[2,2]
The call with current=[1] tries index 1 (the first 2) and recurses. Back in that loop, index 2 is a second 2 with i > start, so it is skipped. The top-level call does the same, which is why [2] appears once.
Complexity
Time: O(n · 2^n) for n numbers. There are at most 2^n subsets, and copying one takes up to n steps. The sort adds O(n log n), which is smaller.
Extra space: O(n), besides the answer: the subset being built and one call for each number in it.
Edge cases and common mistakes
- No skip line. Without the duplicate check,
[1,2,2]returns 8 subsets, with[1,2]and[2]twice each. - Skipping with
i > 0instead ofi > start. That version also skips the second 2 when it is the first number a call tries, so[1,2,2]loses[1,2,2]and[2,2]and returns only 4 subsets:[[],[1],[1,2],[2]]. - Forgetting the comparator. See the sort note above: strings sort differently from numbers.
- Single element.
[0]gives[[],[0]]: the empty subset is always included. - Unsorted input.
[2,1,2,1]sorts to[1,1,2,2]and gives 9 subsets, starting[[],[1],[1,1],[1,1,2],[1,1,2,2],[1,2],...]. Without the sort, equal values are not adjacent and the skip test misses them: the search returns 16 subsets, with repeats such as[2,1]three times. - Negative numbers. They need no special care once the comparator is in place:
[-1,-1,1]gives[[],[-1],[-1,-1],[-1,-1,1],[-1,1],[1]].
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].[2,1,2,1]gives 9 subsets.[10,2,2]gives[[],[2],[2,2],[2,2,10],[2,10],[10]].
