90.子集2

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

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

示例 1：

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

示例 2：

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

Solution

答案视角：

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
public class Solution {
    // 用于存储所有可能的组合结果的列表
    List<List<Integer>> result = new ArrayList<>();
    // 用于存储当前路径的列表
    List<Integer> path = new ArrayList<>();

    // 主要方法，寻找所有可能的子集
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 对输入数组进行排序，以便处理重复元素
        Arrays.sort(nums);
        // 开始深度优先搜索，初始状态为索引 0
        dfs(nums, 0);
        return result;
    }

    // 深度优先搜索方法
    private void dfs(int[] nums, int i) {
        // 每次递归调用都将当前路径（子集）添加到结果列表中
        result.add(new ArrayList<>(path));
        // 如果索引 i 到达数组末尾，结束搜索
        if (i == nums.length) {
            return;
        }

        // 遍历输入数组，从索引 i 开始
        for (int j = i; j < nums.length; j++) {
            // 选择当前数字，添加到路径中
            path.add(nums[j]);
            // 递归调用，继续搜索下一个数字，索引递增
            dfs(nums, j + 1);
            // 回溯，移除当前数字
            path.remove(path.size() - 1);
            // 关键：递归后去除后续重复数字
            // 跳过所有相同的数字以避免重复子集
            while (j < nums.length - 1 && nums[j] == nums[j + 1]) {
                ++j;
            }
        }
    }
}

选择视角

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

public class Solution {
    // 用于存储当前路径的列表
    List<Integer> path = new ArrayList<>();
    // 用于存储所有可能的组合结果的列表
    List<List<Integer>> ans = new ArrayList<>();

    // 主要方法，寻找所有可能的子集
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 对输入数组进行排序，以便处理重复元素
        Arrays.sort(nums);
        // 开始深度优先搜索，初始状态为索引 0
        dfs(0, nums);
        return ans;
    }

    // 深度优先搜索方法
    public void dfs(int i, int[] nums) {
        // 如果索引 i 到达数组末尾，将当前路径（子集）添加到结果列表中
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // 选择当前数字，将其添加到路径中
        path.add(nums[i]);
        // 递归调用，继续搜索下一个数字
        dfs(i + 1, nums);
        // 回溯，移除当前数字
        path.remove(path.size() - 1);

        // 跳过后续重复的数字，避免重复子集
        while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
            i++;
        }

        // 递归调用，跳过当前数字，继续搜索下一个数字
        dfs(i + 1, nums);
    }
}