Start learning free

LESSON 361 OF 569 · BACKTRACKING

Subsets II in Python: Backtracking with Duplicates Skipped

Practice O(n · 2n) Read the full explanation

Given a list nums of integers that may contain duplicates, return every distinct subset of nums: every way to pick some of its numbers, from none of them (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 of a repeated number they use: in [1,2,2], picking the first 2 or the second 2 gives the same subset [2], and it must appear only once.

Sort nums first, and write the numbers of each subset in ascending order. Return the subsets in lexicographic order: compare two subsets number by number, and the first position where they differ decides which one comes first; when one subset is the beginning of the other, the shorter one comes first. So the empty subset always comes first. This is the order in which the search described in the note below finds them.

 

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: The two 2s are alike, so [1,2] and [2] each appear once, whichever 2 they use.
[1] is the beginning of [1,2], so it comes first; every subset that starts with 1 comes before the ones that start with 2.

Example 2:

Input: nums = [0]
Output: [[],[0]]
Explanation: With one number there are two subsets: the empty one, then the number itself.

Example 3:

Input: nums = [4,4,4,1,4]
Output: [[],[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]]
Explanation: Sorted, nums is [1,4,4,4,4]. A subset is fixed by whether it has the 1 and by how many 4s it has, from 0 to 4: 2 · 5 = 10 subsets.

 

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • The same number may appear several times in nums.

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 [2,2] gets its second 2.

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.

STEP 1 OF 11
    Ctrl + Enter to check

    PYTHON · BACKTRACKING

    Subsets Ii in Python, explained

    Problem overview

    The function subsetsWithDup receives a list nums 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 copy of a repeated number they use. In [1, 2, 2], taking the first 2 or the second 2 gives the same subset [2], and it must appear once.

    The answer is also ordered. Each subset is written in ascending order, and the subsets are sorted lexicographically: compare number by number, and when one subset is the beginning of another, the shorter one comes first. For [1, 2, 2] the result is [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. For [4, 4, 4, 1, 4], which sorts to [1, 4, 4, 4, 4], a subset is fixed by whether it has the 1 and by how many 4s it has, from 0 to 4, so there are 2 · 5 = 10 subsets.

    Approach: grow subsets with a loop, skip repeated values

    First, sort nums. Equal numbers then sit side by side, so a repeat can be spotted by comparing a number with the one before it. Sorting also makes every subset come out in ascending order.

    The search is a function that receives start, the first index it may still use, and current, the subset built so far. Every subset the search builds is an answer, not only the full ones, so each call first saves a copy of current. Then a loop picks 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. Passing i + 1 means each position of nums is used at most once and the numbers of a subset stay in index order.

    Duplicates are handled by one line: inside the loop, skip nums[i] when i > start and it equals nums[i - 1]. Within one call, each turn of the loop chooses a different next number. Choosing a second copy of a value that an earlier turn of the same loop already chose would rebuild exactly the same subsets. A copy is still allowed when it is the first one the call tries, at i == start, and that is how [2, 2] gets its second 2.

    The search on [1, 2, 2] behaves like this. Each line shows the depth of the call:

    depth 0: save []
depth 1: save [1]
depth 2: save [1, 2]
depth 3: save [1, 2, 2]
depth 1: skip i=2 (value 2)
depth 1: save [2]
depth 2: save [2, 2]
depth 0: skip i=2 (value 2)

    After [1, 2] and [1, 2, 2] are saved, the call that holds [1] reaches the second 2 at i = 2. That 2 is not the first number this call tried, so it is skipped: [1, 2] already exists. The saves come out in exactly the order the statement asks for.

    The idea is the loop form used for Combination Sum. A skip-or-take form, where each call decides about one number, also finds subsets, but with duplicates it is harder to keep them distinct. In the loop form all the choices for one position are made in one loop, where equal numbers are side by side.

    Step by step

    1. Sort nums in place with sort(), so repeats are adjacent.
    2. Create result, an empty list of subsets.
    3. Start the search with self.backtrack(nums, 0, [], result): from index 0, with an empty subset.
    4. Return result. The helper adds to this same list.
    5. Declare the helper backtrack with nums, start, current and result.
    6. Save a copy of current at the top with current.copy(). There is no if around it, since every call's subset is an answer. A copy is needed because current keeps changing during the search.
    7. Loop i over range(start, len(nums)), the indexes whose numbers could come next. Starting at start instead of 0 keeps each subset in index order. When start is past the last index the loop doesn't run, and that is where the search stops.
    8. Skip repeats. If i > start and nums[i] == nums[i - 1], use continue.
    9. Choose nums[i] by appending it to current.
    10. Recurse with nums, i + 1, current and result.
    11. Undo the choice with current.pop(), so the loop can try the next number with current restored.

    The solution in Python

    class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        self.backtrack(nums, 0, [], result)
        return result

    def backtrack(self, nums, start, current, result):
        result.append(current.copy())
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            current.append(nums[i])
            self.backtrack(nums, i + 1, current, result)
            current.pop()

    The Python details worth a closer look:

    • Why copy(). current is one list that the whole search shares and keeps changing. Appending it directly would store the same list object many times. Without .copy(), the final result for [1, 2, 2] is six empty lists, because by the end every pop() has emptied that one list. current[:] or list(current) also make a copy.
    • sort() works in place. It sorts the caller's list and returns None. After subsetsWithDup([2, 1, 2]), the list that was passed in reads [1, 2, 2]. sorted(nums) would return a new list instead, if the input must stay untouched.
    • continue inside a for loop. It skips the rest of this turn and moves to the next i, so nothing is appended or undone for a skipped number.
    • Negative numbers. Sorting handles them like any others: [-1, -1, 3] gives [[], [-1], [-1, -1], [-1, -1, 3], [-1, 3], [3]].

    Complexity

    Time: O(n · 2^n). A list of n numbers has at most 2^n subsets, and copying one takes up to n steps. Sorting adds O(n log n), which is smaller. With repeated values the number of distinct subsets, and so the work, is lower than that bound.

    Space: besides the answer, O(n): the subset being built and one active call per number in it.

    Edge cases and common mistakes

    • The empty subset. It is always part of the answer and always first. [0] gives [[], [0]].
    • Appending without a copy. For [1, 2, 2] this returns [[], [], [], [], [], []].
    • Forgetting the skip. Without the duplicate test, [1, 2, 2] returns [[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]]: [1, 2] and [2] appear twice.
    • Comparing with 0 instead of start. A test i > 0 skips too much. For [1, 2, 2] it returns [[], [1], [1, 2], [2]] and loses [1, 2, 2] and [2, 2], because the second 2 must be allowed when it is the first number a call tries.
    • Not sorting. Without sorting, equal numbers need not be adjacent, so the comparison with nums[i - 1] misses repeats, and the output order is not the required one.
    • Passing i instead of i + 1. That would let one position be used again and again.

    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].
    • [1, 1, 2, 2] gives 9 subsets: [[], [1], [1, 1], [1, 1, 2], [1, 1, 2, 2], [1, 2], [1, 2, 2], [2], [2, 2]].
    • [1, 2, 3] gives all 8 subsets, since nothing repeats.
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free