一个整数数组 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);//节省空间!
        }
    }
}

Q.E.D.


大力出奇迹