题目

力扣题目链接

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

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

  1. 输入：nums = [1,2,2]
  2. 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

  1. 输入：nums = [0]
  2. 输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

思路

做本题之前一定要先做 78. 子集 。

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

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

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

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

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

本题就是其实就是 78. 子集 的基础上加上了去重，去重我们在 40. 组合总和II 也讲过了。

总结

其实这道题目的知识点，我们之前都讲过了，如果之前讲过的子集问题和去重问题都掌握的好，这道题目应该分分钟AC。

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

  1. if (i > startIndex && nums[i] == nums[i - 1] ) {
  2.         continue;
  3. }

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

答案

Java

  1. class Solution {
  2.     int[] nums = null;
  4.     List<List<Integer>> result = new ArrayList<>();
  5.     LinkedList<Integer> path = new LinkedList<>();
  7.     boolean[] used = null;
  9.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  10.         this.nums = nums;
  11.         used = new boolean[nums.length];
  13.         // 去重需要排序
  14.         Arrays.sort(nums);
  16.         backtracking(0);
  17.         return result;
  18.     }
  20.     void backtracking(int startIndex) {
  21.         result.add(new ArrayList<>(path));
  23.         if (startIndex >= nums.length) {
  24.             return;
  25.         }
  27.         for (int i = startIndex; i < nums.length; i++) {
  28.             // used[i - 1] == true，说明同一树支candidates[i - 1]使用过
  29.             // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  30.             // 而我们要对同一树层使用过的元素进行跳过
  31.             if (i > startIndex  && nums[i] == nums[i - 1] && used[i - 1] == false) {
  32.                 // 其实本题也可以不使用 used 数组来去重，因为递归的时候下一个 startIndex 是 i+1 而不是 0 。
  33.                 // 如果要是全排列的话，每次要从 0 开始遍历，为了跳过已入栈的元素，需要使用 used 。
  34.                 // 也就是说 used[i - 1] == false 这个条件在本题中是不需要的。
  35.                 // 数组排序后，仅用 nums[i] == nums[i - 1] 就可以了。
  36.                 continue;
  37.             }
  39.             path.add(nums[i]);
  40.             used[i] = true;
  43.             backtracking(i + 1);
  45.             path.removeLast();
  46.             used[i] = false;
  47.         }
  48.     }
  49. }

REF

https://programmercarl.com/0090.子集II.html
https://leetcode-cn.com/problems/subsets-ii/