Start learning free

LESSON 361 OF 569 · BACKTRACKING

Subsets II in Java: Backtracking with 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

    JAVA · BACKTRACKING

    Subsets Ii in Java, explained

    Problem overview

    The method subsetsWithDup receives an int[] named nums that may contain repeated numbers and returns a List<List<Integer>> with 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, so in [1,2,2] picking the first 2 or the second 2 gives the same subset [2], and it must be listed once.

    The subsets are written in ascending order and returned in lexicographic order: compare number by number, and when one subset is the beginning of another, the shorter one comes first. For [1,2,2] the answer is [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. For [4,4,4,1,4] the sorted array is [1,4,4,4,4], a subset is fixed by whether it has the 1 and how many 4s it has (0 to 4), and there are 2 · 5 = 10 subsets.

    Approach: choose the next number, and never choose the same value twice in one place

    The lesson uses the loop form of backtracking. A call receives start, the first index it may 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 picks the next number of the subset: for each index i from start on, it adds nums[i], recurses with i + 1 so later numbers come from after this one, and removes the number again.

    Starting the loop at start instead of 0 keeps each subset in index order, so every subset is built once, in ascending order after sorting.

    Duplicates are the new problem. Without handling, [1,2,2] produces [2] twice, once for each 2, and also [1, 2] twice. Running the search without any skip gives [[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]]: eight subsets, two of them repeated.

    The fix is one line, and it needs the array to be sorted so that equal numbers sit side by side. Inside one call, each turn of the loop chooses a different next number. If nums[i] equals nums[i - 1] and i - 1 was already tried as the next number in this same call, choosing the equal value again would rebuild exactly the same subsets. So the loop skips nums[i] when i > start and nums[i] == nums[i - 1]. At i == start nothing was tried before in this call, so the number is taken even when it equals the one before it. That is how [2, 2] gets its second 2: the first 2 is chosen, then the deeper call starts at the next index, where the second 2 is the first number it tries.

    Sorting also gives the output order. Numbers are tried from smallest to largest, and each call saves its subset before extending it, so a subset appears before every subset that extends it, and smaller continuations come before larger ones.

    Step by step

    1. Sort nums with Arrays.sort, in place. Equal numbers become neighbours, and each subset will be written in ascending order.
    2. Create result, an ArrayList of lists.
    3. Start the search at index 0 with an empty list. The helper backtrack is assumed to exist for now.
    4. Return result.
    5. Declare backtrack as a void method taking nums, start, current and result.
    6. Save a copy of current with new ArrayList<>(current). The list keeps changing as the search goes on, so result needs a snapshot. No if is needed, because every subset is an answer.
    7. Loop with i from start to the end of the array.
    8. Skip repeats with continue when i > start and nums[i] == nums[i - 1].
    9. Add nums[i] to the end of current.
    10. Recurse with i + 1, so each number is used at most once and the subset stays in ascending order.
    11. Undo the choice by removing the last element of current, at index current.size() - 1, so the loop can try the next number.

    The solution in Java

    class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

    The details most likely to trip a learner:

    • The copy. result.add(current) would store a reference to the one list that the search keeps changing, and every entry would end up showing the same final state. new ArrayList<>(current) copies the numbers.
    • remove with an int removes by index. On a List<Integer>, remove(int) and remove(Object) are different methods. On the list [5, 6, 7, 1], remove(1) gives [5, 7, 1], while remove(Integer.valueOf(1)) gives [5, 6, 7]. The solution passes current.size() - 1, an int, so it removes the last element, which is what the undo needs.
    • Arrays.sort(nums) sorts the caller's array. That is fine for this lesson, but a method that must keep its input unchanged would sort a copy.

    Complexity

    There are at most 2^n subsets, and copying one takes up to n steps, so the time is O(n · 2^n), with the sort (O(n log n)) included. With ten distinct numbers the method returns 1024 subsets; with ten equal numbers it returns only 11, because the skip prevents duplicates from being built at all rather than filtering them afterwards. Besides the answer, the extra space is O(n): the subset being built and one call per number in it.

    Edge cases and common mistakes

    • Forgetting to sort. The skip compares neighbours, so equal numbers must be adjacent, and the output order depends on sorting.
    • Comparing with i > 0 instead of i > start. That also skips the legitimate second copy at i == start. On [1,2,2] it returns [[], [1], [1, 2], [2]], losing [1, 2, 2] and [2, 2].
    • No skip at all. Duplicate subsets, as shown above.
    • Saving only at full length. Every partial subset counts, including the empty one.
    • Recursing with start + 1 instead of i + 1. The next number must come after the one just chosen.

    Testing

    These inputs were run against the solution above:

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