LeetCode——子集II

NO.90 子集II 中等

思路一：回溯 姊妹题NO.79子集，解决思路一样，不同的就是本题存在重复元素，深搜的时候进行重复元素剪枝即可转化成NO.79的样子。

List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
    if (nums==null||nums.length==0)return res;
    //把重复的元素紧凑到一起
    Arrays.sort(nums);
    dfs(nums,0,new LinkedList<Integer>());
    return res;
}

private void dfs(int[] nums, int idx, LinkedList<Integer> track) {
    res.add(new ArrayList<>(track));
    for (int i = idx; i < nums.length; i++) {
        //重复的剪枝
        if (i>idx&&nums[i]==nums[i-1])continue;
        track.add(nums[i]);
        dfs(nums,i+1,track);
        track.removeLast();
    }
}

时间复杂度：O(n*2^n) n数组元素个数。生成每个子集最多需要n的时间，共有2^n个子集。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github