Problem overview
The function subsets_with_dup receives nums, a vector of integers that may contain repeated values, and returns every distinct subset of it, from the empty subset up to the whole vector. Two subsets are the same when they hold the same numbers the same number of times. In [1, 2, 2], picking the first 2 or the second 2 gives the same subset [2], and it must appear only once.
The result has a fixed shape. The numbers inside each subset are in ascending order, and the subsets themselves are in lexicographic order: compare two subsets number by number, and when one is the beginning of the other, the shorter comes first. For [1, 2, 2] the answer is [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. For [4, 4, 4, 1, 4] it is 10 subsets, because a subset is fixed by whether it has the 1 and how many 4s it has, from 0 to 4: 2 × 5 = 10.
Approach: build subsets by choosing the next number
The lesson sorts nums first. Sorting puts equal numbers next to each other, which makes a repeat easy to spot, and it makes every subset come out in ascending order.
The search is a recursive function with two pieces of state: start, the first index it may still use, and current, the subset built so far. Every subset the search builds is an answer, so each call begins by saving a copy of current. 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 so later numbers come only from after this one, and removes the number again.
That loop would build duplicates, so one line stops them: skip nums[i] when i > start and it equals nums[i - 1]. Inside one call, every turn of the loop picks a different next number. A second copy of the same value as the next number would lead to exactly the same subsets again. At i == start the number is the first this call tries, so it is taken even if it equals the one before it. That is how [2, 2] gets its second 2.
For [1, 2, 2] the calls run like this:
backtrack(start = 0, current = [])
backtrack(start = 1, current = [1])
backtrack(start = 2, current = [1, 2])
backtrack(start = 3, current = [1, 2, 2])
skip i = 2
backtrack(start = 2, current = [2])
backtrack(start = 3, current = [2, 2])
skip i = 2
The calls appear in the same order as the saved subsets. Both skips are the second 2 being offered as the next number after the first 2 was already tried.
Step by step
- Sort
numsin place withsort(). The parameter is declaredmut, so the function may change its own vector. - Create
resultas an empty vector. Rust infersVec<Vec<i32>>from how it is used. - Start the search with
Self::backtrack: a borrow ofnums, start index 0, a fresh empty vector as the current subset, and a mutable borrow ofresult. - Return
resultas the last expression. - Declare the helper
backtrackwithnums: &Vec<i32>,start: usize,current: &mut Vec<i32>andresult: &mut Vec<Vec<i32>>. - Save the subset with
result.push(current.clone())at the top, with no condition. The empty subset, partial subsets and full ones are all answers. The clone is a snapshot, becausecurrentkeeps changing. - Loop
ioverstart..nums.len(), every index whose number could come next. Whenstartis past the last index the loop does not run, which is where the search stops. - Skip repeats with
continuewheni > startandnums[i] == nums[i - 1]. - Choose the number: push
nums[i]ontocurrent. - Recurse with
i + 1as the new start, so each number is used at most once and the subset stays in ascending order. - Undo the choice with
current.pop(), so the loop can try the next number in its place.
The solution in Rust
impl Solution {
fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort();
let mut result = Vec::new();
Self::backtrack(&nums, 0, &mut Vec::new(), &mut result);
result
}
fn backtrack(nums: &Vec<i32>, start: usize, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
result.push(current.clone());
for i in start..nums.len() {
if i > start && nums[i] == nums[i - 1] {
continue;
}
current.push(nums[i]);
Self::backtrack(nums, i + 1, current, result);
current.pop();
}
}
}
The Rust details worth a closer look:
mut nums. The wordmutin the parameter list makes the local binding mutable, sosort()can reorder the vector the function owns. The caller's vector was moved in, so nothing outside sees the change.&mut Vec::new(). This creates a temporary empty vector and lends it mutably for the duration of the call. It lives long enough because the temporary lasts to the end of the statement.- Passing
currentandresulton. Insidebacktrackthey are already&mutreferences, so the recursive call passes them as they are. Rust reborrows them for the call, and they are usable again once it returns. current.clone(). It copies the numbers into a new vector. Pushingcurrentitself is not possible, since it is only borrowed, and it would change afterwards anyway.i - 1with ausize. The expression runs only wheni > start, and because of&&'s short-circuiting,nums[i - 1]is never evaluated ati == 0, where the subtraction would underflow.nums.sort(). Integers have a total order, sosort()works directly, and it is stable. Stability does not matter for plain integers.
Complexity
Time: O(n * 2^n). A vector of n numbers has at most 2^n subsets, and copying one takes up to n steps. Sorting costs O(n log n), which is smaller.
Space: O(n) beyond 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 skip repeats. Without the
continueline,[1, 2, 2]returns[[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]], with[1, 2]and[2]twice. - Comparing with
i > 0instead ofi > start. That skips a repeated number even as the first choice of a call, so[2, 2]can never be built. On[1, 2, 2]it returns only[[], [1], [1, 2], [2]], and on[4, 4, 4, 1, 4]only 4 subsets instead of 10. - Forgetting to sort. Equal numbers are then not neighbours, and the check against
nums[i - 1]misses them. On[2, 1, 2]the search withoutsort()returns[[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]:[2]appears twice, and the subsets are not in ascending order. - Saving only full subsets. Every subset is an answer, including the empty one. The save is at the top of each call, not inside an
if. - Passing
startinstead ofi + 1. The same number could be chosen again and again, so each number would no longer be used at most once. - Forgetting
pop(). The removed number would stay in the subset for the next turns of the loop, and the subsets would no longer match the numbers chosen. - Single element or all equal.
[0]gives[[], [0]], and[3, 3]gives[[], [3], [3, 3]].
Testing
[1, 2, 2]gives[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].[0]gives[[], [0]].[4, 4, 4, 1, 4]gives the 10 subsets[[], [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 the same result as[1, 2, 2], because the order of the input does not matter.[3, 3]gives[[], [3], [3, 3]].
