Start learning free

LESSON 366 OF 574 · BACKTRACKING

Subsets II in Swift: Backtracking with Duplicates Skipped

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

Given an array 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 12
    Ctrl + Enter to check

    SWIFT · BACKTRACKING

    Subsets Ii in Swift, explained

    Problem overview

    The method subsetsWithDup receives nums, 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. In [1, 2, 2], taking the first 2 or the second 2 gives the same subset [2], and it must be listed once.

    Each subset is written in ascending order, and the subsets are returned in lexicographic order: the first position where two subsets differ decides, and a subset that is the beginning of another comes first. For [1, 2, 2] the answer is [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. For [4, 4, 4, 1, 4], which is [1, 4, 4, 4, 4] once sorted, a subset is fixed by whether it has the 1 and by how many 4s it has (0 to 4), so there are 2 · 5 = 10 subsets.

    Approach: choose the next number in a loop

    The search grows a subset one number at a time. A call receives start, the first index it may still use, and current, the subset built so far. It does two things:

    1. It saves a copy of current. Every subset the search builds is an answer, not only the full ones, so there is no condition around this.
    2. It loops over the indexes i from start on. Each turn adds nums[i] to current, calls itself with i + 1, and removes the number again.

    Starting the loop at start and passing i + 1 means a subset takes its numbers in index order, so each index is used at most once and each subset is built only once from a given choice of indexes.

    The duplicates need one more rule. Sort the array first, so equal numbers sit side by side. Inside one call, each turn of the loop picks a different next number for the subset. If nums[i] equals nums[i - 1] and i > start, the previous turn already tried that value as the next number, and trying it again would build exactly the same subsets. So the loop skips it. At i == start nothing was tried in this call yet, so the number is taken even when it equals the one before it. That is how [2, 2] gets its second 2: the first call takes the first 2, and the call below it, with start at the second 2, takes that one.

    Sorting has a second benefit: it writes each subset in ascending order and produces the subsets in the lexicographic order the answer requires.

    Step by step

    1. Sort a copy. Parameters are constants in Swift, so declare a new constant also named nums, set to nums.sorted(). It hides the parameter for the rest of the method.
    2. Create result, an empty [[Int]].
    3. Create current, an empty [Int]: the subset being built.
    4. Start the search with backtrack(nums, 0, &current, &result). Nothing is chosen yet, and every index from 0 on may be used.
    5. Return result.
    6. Declare the helper backtrack with nums, start, and two inout parameters, current and result, so the calls change the same two arrays.
    7. Save the subset at the top: append current to result.
    8. Loop with i over start..<nums.count.
    9. Skip repeats: if i > start && nums[i] == nums[i - 1], do continue.
    10. Choose nums[i] by appending it to current.
    11. Recurse with nums, i + 1, &current and &result.
    12. Undo the choice with current.removeLast(), so the next turn of the loop starts from the same subset.

    The solution in Swift

    class Solution {
    func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
        let nums = nums.sorted()
        var result = [[Int]]()
        var current = [Int]()
        backtrack(nums, 0, &current, &result)
        return result
    }

    func backtrack(_ nums: [Int], _ start: Int, _ current: inout [Int], _ result: inout [[Int]]) {
        result.append(current)
        for i in start..<nums.count {
            if i > start && nums[i] == nums[i - 1] {
                continue
            }
            current.append(nums[i])
            backtrack(nums, i + 1, &current, &result)
            current.removeLast()
        }
    }
}

    The Swift details worth a closer look:

    • sorted() versus sort(). sorted() returns a new array and leaves the original alone, which suits a constant parameter. sort() sorts in place and needs a var.
    • Arrays are values. result.append(current) stores a copy of current. Later append and removeLast calls on current don't change the subsets already saved. In a language where arrays are references, this line needs an explicit copy.
    • inout parameters. The helper changes the caller's current and result, and each call site marks them with &. The calls therefore work on one shared pair of arrays and no big copies are made.
    • start..<nums.count at the end. When start equals nums.count the range is empty and the loop does nothing, which is where the search stops. Since start is at most nums.count, the range is never reversed. A reversed range such as 5..<3 would be a run-time error in Swift.

    Complexity

    Time: O(n · 2^n). There are at most 2^n subsets, and copying one into result takes up to n steps. Sorting costs O(n log n), which is smaller. Skipping repeats only makes the search smaller: for ten equal numbers the method builds 11 subsets, not 1,024. For ten different numbers there are 1,024.

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

    Edge cases and common mistakes

    • No skip at all. On [1, 2, 2] the result becomes [[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]]: [1, 2] and [2] appear twice.
    • Skipping with i > 0 instead of i > start. The second 2 can then never be taken after the first, so [1, 2, 2] gives [[], [1], [1, 2], [2]] and [1, 2, 2] and [2, 2] are lost. The test must compare with start, because a repeat is only redundant when the same call already tried that value.
    • Forgetting to sort. The skip compares neighbours, so equal numbers must be side by side. With the skip but without the sort, the input [2, 1, 2] returns [[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]: [2] appears twice, the subsets are not in ascending order, and the order of the answer is wrong.
    • Forgetting the undo. Without removeLast() the numbers pile up in current and every later subset is wrong.
    • Saving only at the end. A subset is an answer at every call, including the very first one with the empty current. The empty subset is always the first element of the result.

    Testing

    • [1, 2, 2] gives [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].
    • [0] gives [[], [0]].
    • [2, 1, 2] gives [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]], the same as [1, 2, 2].
    • [3, 1] gives [[], [1], [1, 3], [3]].
    • [4, 4, 4, 1, 4] gives 10 subsets: the empty one first and [4, 4, 4, 4] last.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free