Backtracking - 90. Subsets II

leetcode
81

90. Subsets II

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],
  []
]

思路：

于78题相比，这题的数组中的元素可能重复，其实可以先对数组排序，然后再用dfs求解。

代码：

go：

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

	res := [][]int{[]int{}}

	sort.Ints(nums)
    doSubsetsWithDup(nums, []int{}, &res)
	return res
}

func doSubsetsWithDup(nums []int, cur []int, res *[][]int) {
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		cur = append(cur, nums[i])
        *res = append(*res, append([]int{}, cur...))
        
		doSubsetsWithDup(nums[i+1:], cur, res)
		cur = cur[:len(cur)-1]
	}
}