子集问题（二）

#90.子集II

力扣题目链接(opens new window)

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

  • 输入: [1,2,2]
  • 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

#思路

做本题之前一定要先做78.子集 (opens new window)。

这道题目和78.子集 (opens new window)区别就是集合里有重复元素了，而且求取的子集要去重。

那么关于回溯算法中的去重问题，在40.组合总和II (opens new window)中已经详细讲解过了，和本题是一个套路。

剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。

用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）

90.子集II

从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

本题就是其实就是回溯算法：求子集问题！ (opens new window)的基础上加上了去重，去重我们在回溯算法：求组合总和（三） (opens new window)也讲过了

关键点

本题也可以不使用used数组来去重，因为递归的时候下一个startIndex是i+1而不是0。

如果要是全排列的话，每次要从0开始遍历，为了跳过已入栈的元素，需要使用used。

Java代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup( int[] nums ) {
	Arrays.sort(nums);
    backtracking( nums, 0 );
    return res;
}
private void backtracking( int[] nums, int startIndex ) {
	res.add(new ArrayList<>(path));
	for(int i=startIndex;i<nums.length;i++) {
		if(i > startIndex && nums[i] == nums[i-1]) continue;
		path.add(nums[i]);
		backtracking(nums,i+1);
		path.remove(path.size() -1);
	}
}