Backtracking - 90. Subsets II
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]
}
}