Start learning free

LESSON 365 OF 573 · BACKTRACKING

Subsets II in Go: 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

    GO · BACKTRACKING

    Subsets Ii in Go, explained

    Problem overview

    The function subsetsWithDup receives a slice 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, no matter which copy of a repeated number they use. In [1, 2, 2] the first 2 and the second 2 each give the subset [2], and it must appear once.

    The subsets are written in ascending order and returned in lexicographic order: compare two subsets number by number, the first difference 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 [0] it is [[] [0]].

    A subset of repeated numbers is fixed by how many copies of each value it takes. For [4, 4, 4, 1, 4], sorted to [1, 4, 4, 4, 4], it is fixed by whether it has the 1 and how many 4s it has, from 0 to 4. That gives 2 × 5 = 10 subsets.

    Approach: choose the next number in a loop

    The lesson uses backtracking in a loop form. First sort nums, so equal numbers sit next to each other and each subset comes out in ascending order. A call to backtrack gets 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.
    2. It loops over the indices i from start on. Each turn chooses the next number of the subset: add nums[i], recurse with i + 1, then remove the number again.

    Duplicates are handled by one line. Inside one call, each turn of the loop picks a different next number, and picking a second copy of the same value as the next number would rebuild exactly the same subsets. So the loop skips nums[i] when i > start and nums[i] == nums[i-1]. At i == start the number is the first one this call tries, so it is taken even if it equals the number before it. That is how [2, 2] gets its second 2: the recursive call after the first 2 starts at the index of the second 2.

    A different form of backtracking decides, for each number, to take it or skip it. With distinct numbers both forms find the same subsets in a different order. The loop form is easier with duplicates, because all the choices for one position of the subset happen in one loop, where equal values are side by side and the repeats can be skipped.

    Step by step

    1. Sort nums with sort.Ints. Equal numbers become neighbours, each subset is in ascending order, and the subsets come out in the required order.
    2. Create result as an empty [][]int. Each subset is itself a slice.
    3. Start the search with backtrack(nums, 0, []int{}, &result): any index may be used, the subset is empty, and the helper gets the address of result.
    4. Return result once the call is done.
    5. Write the helper backtrack with the parameters nums, start, current and result *[][]int. It returns nothing.
    6. Save a copy of current at the top of the helper, with no if around it. append([]int{}, current...) makes the copy.
    7. Loop with i := start; i < len(nums); i++. Starting at start keeps the numbers of a 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. Take the number: append nums[i] to current.
    10. Recurse with i+1 as the new start, so each number is used at most once.
    11. Undo the choice: current = current[:len(current)-1], so the loop can try the next number in its place.

    The solution in Go

    func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	result := [][]int{}
	backtrack(nums, 0, []int{}, &result)
	return result
}

func backtrack(nums []int, start int, current []int, result *[][]int) {
	*result = append(*result, append([]int{}, current...))
	for i := start; i < len(nums); i++ {
		if i > start && nums[i] == nums[i-1] {
			continue
		}
		current = append(current, nums[i])
		backtrack(nums, i+1, current, result)
		current = current[:len(current)-1]
	}
}

    The Go details worth a closer look:

    • Why copy the subset. current shares its backing array with the slices of other calls, and it keeps changing as the search goes on. Appending current itself would store a slice that later calls overwrite. On [1, 2, 2], a version that saves current without copying returns [[] [2] [1 2] [1 2 2] [2] [2 2]], where the second subset should be [1]. append([]int{}, current...) builds a new slice with its own memory.
    • Why a pointer to the result. append can return a slice with a new backing array, and the helper must put it where subsetsWithDup sees it. With result *[][]int, the assignment *result = append(*result, ...) does that.
    • The undo. current[:len(current)-1] is the slice without its last element. It doesn't clear memory, but the next append overwrites that slot, and the copy saved earlier is unaffected.
    • sort.Ints sorts in place. It reorders the slice the caller passed: calling the function with [3, 1, 3] leaves the caller's slice as [1 3 3].
    • The three-dot spread. In append([]int{}, current...), the ... passes the elements of current as separate arguments.

    Complexity

    Time: O(n · 2^n) for n numbers, sorting included. There are 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) beyond the answer. The subset being built holds at most n numbers, and the recursion is at most n calls deep.

    Edge cases and common mistakes

    • Dropping the skip line. Without it, [1, 2, 2] returns eight subsets: [[] [1] [1 2] [1 2 2] [1 2] [2] [2 2] [2]], with [1 2] and [2] twice.
    • Skipping with i > 0. Comparing against i > 0 instead of i > start also skips the second 2 inside [2, 2], so [1, 2, 2] returns only [[] [1] [1 2] [2]] and loses [1 2 2] and [2 2].
    • Forgetting to sort. The skip line compares neighbours, so equal values must be adjacent. The required order also depends on sorting.
    • Negative numbers. [-1, 1, -1] sorts to [-1, -1, 1] and gives [[] [-1] [-1 -1] [-1 -1 1] [-1 1] [1]].
    • All numbers equal. Ten 7s give 11 subsets, one for each count from 0 to 10, while ten different numbers give 1024.
    • The empty subset. It is always the first element of the answer, as the empty copy saved by the first call.

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