友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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. Subsets 类似。不一样的地方是要处理重复元素:

0090 01

第 4 行新添加的 2 要加到第 3 行的所有解中,而第 3 行的一部分解是旧解,一部分是新解。可以看到,我们黑色部分是由第 3 行的旧解产生的,橙色部分是由新解产生的。

而第 1 行到第 2 行,已经在旧解中加入了 2 产生了第 2 行的橙色部分,所以这里如果再在旧解中加 2 产生黑色部分就造成了重复。

所以当有重复数字的时候,我们只考虑上一步的新解,算法中用一个指针保存每一步的新解开始的位置即可。

如果使用递归回溯来解决这个问题,遇到重复的直接跳过就可以了,因为重复字段已经处理过一次了。

  • 一刷

  • 二刷

  • 三刷

  • 三刷(优化)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Runtime: 2 ms, faster than 27.76% of Java online submissions for Subsets II.
 * Memory Usage: 39.4 MB, less than 5.88% of Java online submissions for Subsets II.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-02-05 21:28
 */
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(nums, 0, new ArrayDeque<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, Deque<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i - 1] == nums[i]) {
            continue;
        }
        int num = nums[i];
        current.addLast(num);
        backtrack(nums, i + 1, current, result);
        current.removeLast();
    }
}

/**
 * Runtime: 2 ms, faster than 27.76% of Java online submissions for Subsets II.
 * Memory Usage: 39.3 MB, less than 5.88% of Java online submissions for Subsets II.
 *
 * Copy from: https://leetcode-cn.com/problems/subsets-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-19/[详细通俗的思路分析,多解法 - 子集 II - 力扣(LeetCode)]
 */
public List<List<Integer>> subsetsWithDupAppend(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(Collections.emptyList());
    Arrays.sort(nums);
    //保存新解的开始位置
    int start = 1;
    for (int i = 0; i < nums.length; i++) {
        List<List<Integer>> temp = new LinkedList<>();
        for (int j = 0; j < result.size(); j++) {
            //如果出现重复数字,就跳过所有旧解
            if (i > 0 && nums[i - 1] == nums[i] && j < start) {
                continue;
            }
            List<Integer> list = result.get(j);
            List<Integer> newList = new ArrayList<>(list);
            newList.add(nums[i]);
            temp.add(newList);
        }
        start = result.size();
        result.addAll(temp);
    }
    return result;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-07-08 21:31:11
 */
public List<List<Integer>> subsetsWithDup(int[] nums) {
  List<List<Integer>> result = new ArrayList<>();
  Arrays.sort(nums); // 对数组进行排序,方便后续处理相同的元素
  backtrack(nums, 0, result, new ArrayList<>());
  return result;
}

private void backtrack(int[] nums, int start,
                       List<List<Integer>> result, List<Integer> subset) {
  result.add(new ArrayList<>(subset));
  for (int i = start; i < nums.length; i++) {
    // 在同一父节点下的递归子树,对值相同的节点进行剪枝
    if (start < i && nums[i - 1] == nums[i]) {
      continue;
    }
    subset.add(nums[i]);
    backtrack(nums, i + 1, result, subset);
    subset.remove(subset.size() - 1);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-09 18:04:54
 */
public List<List<Integer>> subsetsWithDup(int[] nums) {
  List<List<Integer>> result = new ArrayList<>();
  Arrays.sort(nums);
  result.add(new ArrayList<>());
  // 使用 Set 记录已添加的子集,这个方案还需要再优化
  Set<String> existed = new HashSet<>();
  for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    int size = result.size();
    for (int j = 0; j < size; j++) {
      List<Integer> subset = new ArrayList<>(result.get(j));
      subset.add(num);
      StringBuilder sb = new StringBuilder(nums.length);
      for (Integer ai : subset) {
        sb.append(ai);
      }
      if (existed.add(sb.toString())) {
        result.add(subset);
      }
    }
  }
  return result;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-10 11:38:25
 */
public List<List<Integer>> subsetsWithDup(int[] nums) {
  Arrays.sort(nums);
  int length = nums.length;
  List<List<Integer>> result = new ArrayList<>((int) Math.pow(2, length));
  result.add(new ArrayList<>());
  int start = 0;
  Integer prev = null;
  for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    int size = result.size();
    int j = 0;
    // 如果与前一个元素相同,则只需要处理上次添加的子集即可
    if (prev != null && num == prev) {
      j = start;
    }
    for (; j < size; j++) {
      List<Integer> subset = result.get(j);
      List<Integer> ns = new ArrayList<>(subset);
      ns.add(num);
      result.add(ns);
    }
    prev = num;
    start = size;
  }
  return result;
}