子集II

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode每日一题，90. 子集 II

先看题目描述

ck90Ag.png

算法和思路

回溯

这题可以用回溯解决，回溯实际上就是对树的一个深度优先搜索，树的不同分支就对应着不同选择

如果这题没有重复数字，那么树的每个非叶子节点会有两个分支，分别对应着某数字出现与不出现的两种情况；而这题的数组里会有重复数字，那么情况就复杂些，先对数组排序，然后遍历数字，若某数字重复 n 次，那么就有 n + 1 种选择，对应着该数字出现 0 次到 n 次的情况，即该节点会有 n + 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
28
29
30
31
32
33
class Solution {
    List<List<Integer>> res = new ArrayList<>();

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

    public void dfs(int[] nums, int i, List<Integer> cur) {
        if (i == nums.length) {
            res.add(new ArrayList(cur));
            return;
        }
        int num = nums[i];
        int n = 0;
        while (i < nums.length && nums[i] == num) {
            i++;
            n++;
        }
        dfs(nums, i, cur);
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < j; k++) {
                cur.add(num);
            }
            dfs(nums, i, cur);
            for (int k = 0; k < j; k++) {
                cur.remove(cur.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
class Solution {
    List<List<Integer>> res = new ArrayList<>();

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

    public void dfs(boolean flag, int[] nums, int i, List<Integer> cur) {
        if (i == nums.length) {
            res.add(new ArrayList(cur));
            return;
        }
        dfs(false, nums, i + 1, cur);
        if (!flag && i > 0 && nums[i] == nums[i - 1]) {
            return;
        }
        cur.add(nums[i]);
        dfs(true, nums, i + 1, cur);
        cur.remove(cur.size() - 1);
    }
}