Start learning free

LESSON 365 OF 573 · BACKTRACKING

Subsets II in Scala: Backtracking with Duplicate Skipping

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 11
    Ctrl + Enter to check

    SCALA · BACKTRACKING

    Subsets Ii in Scala, explained

    Problem overview

    The method subsetsWithDup receives an Array[Int] called nums that may contain repeated numbers. It returns every distinct subset as a List[List[Int]], from the empty subset to the one holding all the numbers. Two subsets are the same when they hold the same numbers the same number of times, so in [1,2,2] picking the first 2 or the second 2 gives the same subset [2], which must appear once.

    The order is fixed too. Each subset is written in ascending order, and the subsets are in lexicographic order: the first position where two subsets differ decides, and a subset that is the beginning of another comes first. The empty subset is always first.

    For [1,2,2] the answer is List(List(), List(1), List(1, 2), List(1, 2, 2), List(2), List(2, 2)): six subsets, where plain subsets of three numbers would give eight. For [4,4,4,1,4] there are only ten: a subset is fixed by whether it has the 1 and by how many 4s it has, from 0 to 4, which is 2 times 5.

    Approach: sort, then pick the next number in a loop

    Sorting nums puts equal numbers next to each other, which makes repeats easy to recognise, and it makes every subset come out in ascending order.

    The search uses the loop form of backtracking. A call receives 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 first saves a copy of current. Then a loop chooses the next number of the subset: for each index i from start, it adds nums(i), calls itself with i + 1, and removes the number again.

    Duplicates are handled by one condition. Inside one call, each turn of the loop picks a different next number. If nums(i) equals nums(i - 1) and i > start, this call has already tried that value as the next number, and trying it again would rebuild the same subsets. So that turn is skipped. A repeated value is still taken when it is the first one this call tries, at i == start: that is how [2,2] gets its second 2.

    Step by step

    1. Sort nums in place with scala.util.Sorting.quickSort(nums).
    2. Create result, an empty ArrayBuffer[List[Int]](). Each subset is itself a list.
    3. Start the search with backtrack(nums, 0, ArrayBuffer[Int](), result): nothing chosen, every index available.
    4. Return result.toList as the last expression.
    5. Write the helper backtrack with nums, start, current and result, returning Unit.
    6. Save a snapshot of the current subset at the top: result += current.toList. There is no condition around it, because every subset along the way is an answer.
    7. Loop with i over start until nums.length. Starting at start keeps each subset in index order, so in ascending order. When start is past the last index the loop is empty, and that is where the search ends.
    8. Skip repeats with if (i == start || nums(i) != nums(i - 1)). Scala has no continue, so the rest of the loop body goes inside this if.
    9. Choose nums(i): current += nums(i).
    10. Explore with backtrack(nums, i + 1, current, result). Passing i + 1 means each number is used at most once.
    11. Undo the choice with current.remove(current.length - 1), so the loop can try the next number.

    The solution in Scala

    class Solution {
    def subsetsWithDup(nums: Array[Int]): List[List[Int]] = {
        scala.util.Sorting.quickSort(nums)
        val result = ArrayBuffer[List[Int]]()
        backtrack(nums, 0, ArrayBuffer[Int](), result)
        result.toList
    }

    def backtrack(nums: Array[Int], start: Int, current: ArrayBuffer[Int], result: ArrayBuffer[List[Int]]): Unit = {
        result += current.toList
        for (i <- start until nums.length) {
            if (i == start || nums(i) != nums(i - 1)) {
                current += nums(i)
                backtrack(nums, i + 1, current, result)
                current.remove(current.length - 1)
            }
        }
    }
}

    Scala details worth a look:

    • current.toList is a copy. current is one ArrayBuffer that the search keeps changing. Storing the buffer itself would put the same object into result many times. With result += current on [1,2,2], the six saved items all end up as empty buffers when the search finishes: ArrayBuffer(ArrayBuffer(), ArrayBuffer(), ArrayBuffer(), ArrayBuffer(), ArrayBuffer(), ArrayBuffer()). toList builds an immutable list with the numbers at that moment.
    • quickSort sorts the argument. scala.util.Sorting.quickSort(nums) reorders the caller's array: after the call with Array(3,1,2), that array holds 1, 2, 3. The lesson does it this way. To keep the original order, sort a copy.
    • remove(index) on an ArrayBuffer takes an index, not a value. Here it always removes the last element, at current.length - 1.
    • 0 until n and start until nums.length exclude the end, so i is always a valid index.
    • Short-circuit ||. When i == start is true, nums(i - 1) is not evaluated, so the first turn of a call at start == 0 does not read index -1.

    Complexity

    Time: O(n * 2^n). A set of n numbers has at most 2^n subsets, and copying one with toList takes up to n steps. Sorting costs O(n log n), which is smaller.

    Space: O(n) beyond the answer: the subset being built and one call for each number in it.

    Edge cases and common mistakes

    • No duplicate check. Without the if, [1,2,2] produces eight subsets, with List(1, 2) and List(2) twice: List(List(), List(1), List(1, 2), List(1, 2, 2), List(1, 2), List(2), List(2, 2), List(2)).
    • Comparing with i == 0 instead of i == start. Then the second 2 is skipped even when it is the first choice of its call, and [1,2,2] gives only List(List(), List(1), List(1, 2), List(2)): the subsets [1,2,2] and [2,2] are lost.
    • Not sorting. Equal numbers must be neighbours for the comparison with nums(i - 1) to find them. Sorting also gives the order the answer needs.
    • Passing i instead of i + 1. A number could then be chosen again right after itself, so the subsets would no longer use each number at most once.
    • Forgetting the undo. Numbers would pile up in current and later subsets would contain numbers from earlier ones.
    • A single number. [0] gives List(List(), List(0)).

    Testing

    • [1,2,2] gives List(List(), List(1), List(1, 2), List(1, 2, 2), List(2), List(2, 2)).
    • [0] gives List(List(), List(0)).
    • [4,4,4,1,4] gives ten subsets, from List(), List(1), List(1, 4) up to List(4, 4, 4, 4).
    • [2,1,2,1] gives List(List(), List(1), List(1, 1), List(1, 1, 2), List(1, 1, 2, 2), List(1, 2), List(1, 2, 2), List(2), List(2, 2)).
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free