【每日一题】子集

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

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

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

示例 1：

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

回溯：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;//前置条件
        Arrays.sort(nums);//排序，确保所有方案都具有单调性
        backtrack(0, nums, res, new ArrayList<>());//第一次搜索
        return res;

    }

    public void backtrack(int idx, int[] nums, List<List<Integer>> res, List<Integer> tmp_list) {
        res.add(new ArrayList<>(tmp_list));//每次搜索当前元素,先把当前元素的链表或传进来的链表加载成一条新链表压进res
        for (int i = idx; i < nums.length; i++) {
            if (i > idx && nums[i - 1] == nums[i]) continue;//当i > idx，意思如果进入某一子循环，且当前元素与上一元素相等，则直接continue
            tmp_list.add(nums[i]);//正常往当前链表加入元素
            backtrack(i + 1, nums, res, tmp_list);
            tmp_list.remove(tmp_list.size() - 1);//节省空间!
        }
    }
}