子集II

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

方法一：回溯

在阅读此题解前可查看前置问题子集。

以数组[1,2,3]为例，在子集问题中我们的搜索路径如下图所示：

类似的，我们画出数组[1,2,2]的搜索路径：

可以看到[1,2] 和 [2] 出现了两次，我们在搜索的过程中需要剪枝。并且，nums 数组必须排序才能保证相同的解只出现在同一层。

下面以不排序的数组 [2,3,2]为例，画出搜索路径：

在遍历到第二个[2,3]时，我们发现不了前面是否遍历过[2,3]这个子集，排序后搜索路径为：

我们只用保存前一个遍历过的数字，再后续的遍历过程中，如果遇到相同的数字直接跳过即可。

class Solution {
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(nums, 0, new ArrayDeque<Integer>());
        return ans;
    }

    private void dfs(int[] nums, int start, Deque<Integer> path){
        ans.add(new ArrayList<Integer>(path));

        int pre = -10;
        for(int i = start; i < nums.length; i++){
            if(nums[i] != pre){
                path.addLast(nums[i]);
                dfs(nums, i + 1, path);
                path.removeLast();
                pre = nums[i];
            }
        }
    }
}

• 时间复杂度O(n * 2 ^ n)
• 空间复杂度O(n)