做本题之前一定要先做78.子集
这道题目和78.子集的唯一区别就是集合里有重复元素了，而且求取的子集要去重。
那么关于回溯算法中的去重问题，在40.组合总和II 中已经详细讲解过了，和本题是一个套路。
剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要，我们做的是“树层去重”。
用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！
本题就是其实就是回溯算法：求78.子集的基础上加上了去重，去重我们在回溯算法：40.组合总和II 也讲过了，所以我就直接给出代码了：
Go代码如下：
func subsetsWithDup(nums []int) [][]int {
if len(nums) == 0 {
return nil
}
res := make([][]int,0)
path := make([]int,0)
used := make([]bool,len(nums))
//注意，既然要去重，首先得让数组是有序的
sort.Ints(nums)
backtracking(nums,&res,&path,0,used)
return res
}
func backtracking(nums []int,res *[][]int,path *[]int,startIndex int,used []bool) {
// 每个子集加入最终结果集
*res = append(*res,append([]int(nil),*path...))
for i := startIndex;i < len(nums);i++ {
// 去重 注意保证i > 0,否则会出现切片下标越界错误
if i > 0 && nums[i] == nums[i - 1] && !used[i-1] {
continue
}
*path = append(*path,nums[i])
used[i] = true
backtracking(nums,res,path,i + 1,used)
*path = (*path)[0:len(*path) - 1]
used[i] = false
}
}
