90. Subsets II #

Problem #

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Problem Summary #

Given an integer array nums that may contain duplicate elements, return all possible subsets (the power set) of the array. Note: The solution set must not contain duplicate subsets.

Solution Approach #

This problem is an enhanced version of Problem 78. Compared with Problem 78, it adds one condition: numbers in the array may be duplicated.
The solution method is still DFS, but some checks need to be added during the backtracking process.
This problem is similar to Problems 78 and 491, so they can be solved and reviewed together.

Code #


package leetcode

import (
	"fmt"
	"sort"
)

func subsetsWithDup(nums []int) [][]int {
	c, res := []int{}, [][]int{}
	sort.Ints(nums) // This is the key logic for deduplication
	for k := 0; k <= len(nums); k++ {
		generateSubsetsWithDup(nums, k, 0, c, &res)
	}
	return res
}

func generateSubsetsWithDup(nums []int, k, start int, c []int, res *[][]int) {
	if len(c) == k {
		b := make([]int, len(c))
		copy(b, c)
		*res = append(*res, b)
		return
	}
	// i will at most be n - (k - c.size()) + 1
	for i := start; i < len(nums)-(k-len(c))+1; i++ {
		fmt.Printf("i = %v start = %v c = %v\n", i, start, c)
		if i > start && nums[i] == nums[i-1] { // This is the key logic for deduplication: do not take the duplicate number this time; the next loop may take the duplicate number
			continue
		}
		c = append(c, nums[i])
		generateSubsetsWithDup(nums, k, i+1, c, res)
		c = c[:len(c)-1]
	}
	return
}