LeetCode 90. Subsets II

Problem

LeetCode 90. Subsets II

1. 题目简述

给出一列整数（可能重复），找出其所有不重复的子集合（包括空集）。例如：

Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

2. 算法思路

这道题就是LeetCode 78. Subsets的进阶版，和LeetCode 40. Combination Sum II特别像，连去重的方式都一模一样，这个必须要记住！！！

注意:这里需要排序，因为要去重！！！

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 这次就必须要sort了，为什么呢？因为我们要去重，例子中的[1,2]只能有一个。和combination sum 2的去重方式可以一致。每次遍历重复的数只用一次。
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList();
        LinkedList<Integer> path = new LinkedList();

        res.add(new ArrayList(path));
        getAllSubsets(nums, 0, res, path);

        return res;
    }

    private void getAllSubsets(int[] nums, int start, List<List<Integer>> res, LinkedList<Integer> path) {
        for (int i = start; i < nums.length; i++) {
            // 注意，这里的去重很精髓，通过i > start这么个判断条件，使得每种重复的数字只会用一次，比如[1,2,2,2]只会出现一次。细品！！！
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            res.add(new ArrayList(path));
            getAllSubsets(nums, i + 1, res, path);
            path.removeLast();
        }
    }
}