LeetCode90-子集II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/subsets-ii/

中文链接：https://leetcode-cn.com/problems/subsets-ii/

题目详述

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

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

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

题目详解

DFS，回溯。在 LeetCode78-子集 的基础上改为了数组中可能存在重复的元素，思路是一致的，不过需要跳过重复的元素。

  • 首先对数组进行排序。
  • 将当前集合加入到结果集中。
  • 枚举每一个可能的元素，如果重复则跳过。
  • 进入下一层将当前元素加入临时集合中。
  • 递归进入下一层，传入的是当前位置的下一个位置。
  • 恢复原状。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00090 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 先排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        dfs(0, nums, res, new ArrayList<>());
        return res;
    }

    private void dfs(int s, int[] nums, List<List<Integer>> res, ArrayList<Integer> list) {
        res.add(new ArrayList<>(list));
        for (int i = s; i < nums.length; ++i) {
            // 去重
            if (i > s && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            dfs(i + 1, nums, res, list);
            list.remove(list.size() - 1);
        }
    }
}

同样，还可以从空集开始，通过逐步添加元素的方法来得到所有的子集。

  • 首先对数组进行排序。

  • 往结果集中添加一个空集。

  • 遍历数组 nums，如果重复则从上次新添加的位置开始添加元素，这样可以跳过重复元素。
  • 遍历原来所有的子集，把原来子集拷贝一份，再把当前元素添加入这个子集，得到新的子集。
  • 两重循环完成后，就得到了结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00090 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 先排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        // 添加一个空集
        res.add(new ArrayList<>());
        int size = 0;
        // 枚举每一个元素
        for (int i = 0; i < nums.length; ++i) {
            // 跳过重复的部分，从上一次新添加的位置开始添加当前元素
            int s = (i > 0 && nums[i] == nums[i - 1]) ? size : 0;
            size = res.size();
            for (int j = s; j < size; ++j) {
                // 拷贝一份
                List<Integer> list = new ArrayList<>(res.get(j));
                list.add(nums[i]);
                res.add(list);
            }
        }
        return res;
    }
}