文章目录
- 90. 子集 II
- 思路
- 补充
- 总结
90. 子集 II
90. 子集 II
给你一个整数数组 nums
,其中可能包含重复元素,请你返回该数组所有可能的
子集(幂集)。
子集:数组的 子集 是从数组中选择一些元素(可能为空)。
解集 不能
包含重复的子集。返回的解集中,子集可以按 任意顺序
排列。
示例 1:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
思路
做本题之前一定要先做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] = truebacktracking(nums,res,path,i + 1,used)*path = (*path)[0:len(*path) - 1]used[i] = false}
}
补充
本题也可以不使用used
数组来去重,因为递归的时候下一个startIndex
是i+1
而不是0
。
如果要是全排列的话,每次要从0
开始遍历,为了跳过已入栈的元素,需要使用used
。
代码如下:
func subsetsWithDup(nums []int) [][]int {if len(nums) == 0 {return nil}res := make([][]int,0)path := make([]int,0)//注意,既然要去重,首先得让数组是有序的sort.Ints(nums)backtracking(nums,&res,&path,0)return res
}func backtracking(nums []int,res *[][]int,path *[]int,startIndex int) {// 每个子集加入最终结果集*res = append(*res,append([]int(nil),*path...))for i := startIndex;i < len(nums);i++ {// 对同一树层使用过的元素进行跳过if i > startIndex && nums[i] == nums[i - 1] { // 注意这里使用i > startIndexcontinue}*path = append(*path,nums[i])backtracking(nums,res,path,i + 1)*path = (*path)[0:len(*path) - 1]}
}
总结
其实这道题目的知识点,我们之前都讲过了,如果之前讲过的子集问题和去重问题都掌握的好,这道题目应该分分钟AC
。