78. 子集

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

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

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

标准的回溯解法，说两点：
1.start表示数组元素要推进；
2.因为空数组也是子集，所以每一次递归都要添加trace，一直到trace.size() == nums.length。

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> trace = new LinkedList<>();
        int start = 0;
        backTrace(nums, start, trace);

        return res;
    }

    public void backTrace(int[] nums, int start, LinkedList<Integer> trace) {
        res.add(new LinkedList<>(trace));
        if (trace.size() == nums.length) {
            return;
        }

        for (int i = start; i < nums.length; i++) {
            // 做选择
            trace.add(nums[i]);
            // 进入下一层
            backTrace(nums, i + 1, trace);
            //回溯
            trace.removeLast();
        }
    }
}

结果如下：

90. 子集 II

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

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

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

跟上题类似，我的解法比较麻烦是因为去重的方法是先对数组进行排序，然后再去重添加。

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        LinkedList<Integer> trace = new LinkedList<>();
        int start = 0;
        backTrace(nums, start, trace);

        return res;
    }

    public void backTrace(int[] nums, int start, LinkedList<Integer> trace) {
        List<Integer> tmp = new LinkedList<>(trace);
        // 添加子集
        if (!res.contains(tmp)) {
            res.add(tmp);
        }
        if (trace.size() == nums.length) {
            return;
        }

        for (int i = start; i < nums.length; i++) {
            // 做选择
            trace.add(nums[i]);
            // 进入下一层
            backTrace(nums, i + 1, trace);
            //回溯
            trace.removeLast();
        }
    }
}

结果如下：