You get an array nums of integers. A number may repeat. Return every distinct subset of nums.
A subset is any choice of some of the numbers. It can hold none of them (the empty subset) or all of them.
Copies of a number count as the same. Either 5 in [5,5,8] gives the same subset [5]. List it only once.
Write each subset in ascending order. List the subsets in lexicographic order. The first position where two subsets differ decides which comes first. If one subset is the start of another, the shorter one comes first.
The empty subset is always first. The search in the Note below finds the subsets in this order.
Example 1:
Input: nums = [3,1,3] Output: [[],[1],[1,3],[1,3,3],[3],[3,3]] Explanation: Sorting nums gives [1,3,3]. The two 3s count as the same. So [1,3] and [3] are listed once each. [1] is the start of [1,3], so [1] comes first. Subsets that start with 1 come before those that start with 3.
Example 2:
Input: nums = [-2] Output: [[],[-2]] Explanation: One number gives two subsets: the empty one, then [-2].
Example 3:
Input: nums = [6,6,6] Output: [[],[6],[6,6],[6,6,6]] Explanation: All the numbers are 6. A subset takes none, one, two or all three of them.
Constraints:
numsholds 1 to 10 numbers.- Each number is between -10 and 10.
- A number may appear more than once.
Note:
The tutorial uses backtracking in the loop form of Combination Sum. Sort nums, so that equal numbers sit next to each other. A call gets start, the first index it may still use, and current, the subset built so far. It first saves a copy of current: every subset the search builds is an answer, not only the full ones. 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, and removes the number again.
The duplicates are handled by one line: the loop skips nums[i] when i > start and nums[i] equals nums[i - 1]. Inside one call, every turn of the loop picks a different next number, and taking a second copy of the same value as the next number would build exactly the same subsets again. A copy is still taken when it is the first one this call tries, at i = start: that is how [3,3] gets its second 3.
Subsets used the other form: each call decided about one number, skip or take, and only the calls that had decided about every number saved a subset. With distinct numbers, both forms find the same subsets, only in a different order. The loop form makes duplicates easy: all the choices for one position of the subset are made in one loop, where equal numbers are side by side and the repeats can be skipped.
There are at most 2n subsets and copying one takes up to n steps, so the time is O(n · 2n), sorting included. Besides the answer, the extra space is O(n): the subset being built and one call per number in it.
Free plan: 30 tutor messages. PRO is unlimited.
