Subsets II

Medium

The problem

Like finding all subsets, but nums may contain repeated numbers. Return every different subset, with no subset appearing twice. They can come in any order.

Example 1
Input: nums = [1, 2, 2]
Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Choosing the first 2 or the second 2 gives the same subset, so each is listed only once.
Example 2
Input: nums = [0]
Output: [[], [0]]

Limits

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
nums can be in any order and can contain repeats
The order of subsets does not matter

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Duplicates in the input create duplicate subsets. Sorting puts equal numbers together — then what rule skips them?

The idea

Sort. In the loop at a given depth skip nums[j] if j > start and nums[j] == nums[j−1].

Target: O(n · 2^n) time

Go function shape

func subsetsWithDup(nums []int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// SubsetsWithDup: sort first so equal numbers are neighbours, then at each depth skip a number that equals the
// previous one in the same loop. That stops the same subset from being built twice.
func SubsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	out := [][]int{}
	var path []int
	var dfs func(start int)
	dfs = func(start int) {
		out = append(out, append([]int{}, path...)) // copy: path keeps changing
		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				continue // same choice as the previous sibling
			}
			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1] // un-choose
		}
	}
	dfs(0)
	return out
}

Read the lesson: Backtracking