题目描述

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

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

样例

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

算法分析

先对数组从小到大排序，每个数有选和不选两种情况，若选的话，假设上一个数与当前数一致，且上一个数没有选，则当前数一定不能选，否则会产生重复情况

时间复杂度 $O(2^n)$

Java 代码

class Solution {
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static List<Integer> path = new ArrayList<Integer>();
    static boolean[] st;
    static void dfs(int[] nums,int u)
    {
        if(u == nums.length)
        {
            ans.add(new ArrayList<Integer>(path));
            return ;
        }

        //不放
        dfs(nums,u + 1);

        //放
        if(u > 0 && nums[u] == nums[u - 1] && !st[u - 1]) return ;
        st[u] = true;
        path.add(nums[u]);
        dfs(nums,u + 1);
        path.remove(path.size() - 1);
        st[u] = false;

    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans.clear();
        Arrays.sort(nums);
        st = new boolean[nums.length + 10];
        dfs(nums,0);
        return ans;
    }
}