Start learning free

LESSON 365 OF 573 · BACKTRACKING

Subsets II in Kotlin: Backtracking with Sorted Duplicates

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

    KOTLIN · BACKTRACKING

    Subsets Ii in Kotlin, explained

    Problem overview

    The method subsetsWithDup receives nums, an IntArray of up to 10 integers that may repeat. It returns every distinct subset: every way to pick some of the numbers, from none (the empty subset) to all. 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 one subset, [2], which must appear once.

    The answer has a fixed order too. Each subset is written in ascending order, and the subsets are in lexicographic order: the first position where two subsets differ decides which comes first, and a subset that is the beginning of another comes before it. The empty subset is therefore first. For [1,2,2] the answer is [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].

    Approach: grow subsets by choosing the next number

    Every subset is a sequence of numbers taken in index order. Backtracking builds them one number at a time. A call receives current, the subset built so far, and start, the first index it may still use. It saves a copy of current right away, because every subset along the way is an answer, not only the full ones. Then a loop tries every index i from start on as the next number: add nums[i], recurse with i + 1, remove it again.

    Starting the loop at start instead of 0 keeps each subset in index order, so no subset is built twice by picking the same indexes in a different order.

    Duplicates need one more idea. Sort nums so that equal numbers sit side by side. Inside one call, each turn of the loop picks a different candidate for the 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 the loop skips it. At i == start the number is the first this call tries, and it is taken even when it equals the number before it. That is how [2, 2] gets its second 2: the first 2 is chosen by one call, and the next call starts right after it, where the second 2 is its first candidate.

    Sorting also puts the numbers of each subset in ascending order and makes the subsets come out in the required order.

    Step by step

    1. Sort nums in place with sort(). Duplicates become neighbours, which makes them easy to detect.
    2. Create result with mutableListOf<List<Int>>(): a list that holds lists.
    3. Start the search with backtrack(nums, 0, mutableListOf(), result): index 0 is the first usable index, and the subset is empty.
    4. Return result after the call.
    5. Declare backtrack with nums, start, current and result.
    6. Save a snapshot of current with current.toList(), at the top and without any condition.
    7. Loop i over start until nums.size. When start is past the last index, the loop does not run, and that is where the recursion ends.
    8. Skip repeats: if i > start and nums[i] == nums[i - 1], use continue.
    9. Choose nums[i] by adding it to the end of current.
    10. Explore by calling backtrack with i + 1, so each number is used at most once.
    11. Undo the choice with removeAt(current.size - 1), so the loop can try the next number on the same current.

    The solution in Kotlin

    class Solution {
    fun subsetsWithDup(nums: IntArray): List<List<Int>> {
        nums.sort()
        val result = mutableListOf<List<Int>>()
        backtrack(nums, 0, mutableListOf(), result)
        return result
    }

    fun backtrack(nums: IntArray, start: Int, current: MutableList<Int>, result: MutableList<List<Int>>) {
        result.add(current.toList())
        for (i in start until nums.size) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue
            }
            current.add(nums[i])
            backtrack(nums, i + 1, current, result)
            current.removeAt(current.size - 1)
        }
    }
}

    Kotlin details worth knowing:

    • IntArray.sort() sorts in place and returns nothing, so the caller's array ends up sorted. That is fine here. The function sorted() would return a new List instead and leave the array as it was.
    • Why toList(). current is one list that keeps changing during the whole search. Adding it directly would store the same list many times, and by the end it would be empty again. With result.add(current) in place of the copy, the call on [1,2,2] returns [[], [], [], [], [], []]: six references to one empty list. toList() stores a snapshot.
    • mutableListOf() without a type is accepted in the call because Kotlin infers MutableList<Int> from the parameter type.
    • removeAt versus remove. On a MutableList<Int>, removeAt(index) removes by position. Use it here, since the last element is what must go.
    • continue skips the rest of the current turn of the for loop and moves to the next i.

    Tracing the example

    Printing each call and each skip while the search runs on [1,2,2] gives:

    backtrack(start=0, current=[])
  backtrack(start=1, current=[1])
    backtrack(start=2, current=[1, 2])
      backtrack(start=3, current=[1, 2, 2])
   i=2: skip (2 again)
  backtrack(start=2, current=[2])
    backtrack(start=3, current=[2, 2])
 i=2: skip (2 again)

    The first skip is in the call with current=[1]: at i=1 it takes the first 2, and at i=2 the second 2 would only repeat what the first one built. The second skip is the same situation in the first call. Each call saves its current when it starts, which produces the six subsets in order.

    Complexity

    Time: O(n · 2^n). A set 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) besides the answer: the subset under construction and one call for each number in it.

    Edge cases and common mistakes

    • One number. [0] gives [[], [0]].
    • Unsorted input. [4,4,4,1,4] becomes [1,4,4,4,4] after sorting, and the answer has 10 subsets: with or without the 1, times 0 to 4 fours. [2,1,2] gives the same result as [1,2,2].
    • All numbers equal. Ten 1s give 11 subsets, one for each count from 0 to 10.
    • All numbers different. [3,1,2] gives [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]], and the numbers 1 to 10 give 1024 subsets, which is 2^10.
    • Negative numbers. [-1,-1] gives [[], [-1], [-1, -1]].
    • Forgetting the skip. Without the continue test, [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 > 0 instead of i > start. The skip then fires for the second 2 even when it is the first candidate of its call, and the result for [1,2,2] is [[], [1], [1, 2], [2]]: both [1, 2, 2] and [2, 2] are missing.
    • Forgetting to sort. With [2,1,2] left unsorted, the equal 2s are not neighbours, the check fails to see them, and the result is [[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]: not in ascending order and with [2] twice.

    Testing

    • [1,2,2] gives [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].
    • [0] gives [[], [0]].
    • [4,4,4,1,4] gives [[], [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 [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].
    • [-1,-1] gives [[], [-1], [-1, -1]].
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free