0090. Subsets II - kumaeki/LeetCode GitHub Wiki

0090. Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2]

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

Example 2:

Input: nums = [0]

Output: [[],[0]]

Constraints:

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

解法1

穷举.

关键在于怎么避免重复.

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(res, new ArrayList<Integer>(), nums, 0);
        return res;
    }

    
    private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, int i) {
        res.add(list);
        // 从第一个开始, 每次都在前一次计算的基础上加一个数字
        for (int j = i; j < nums.length; j++) {
            // 在当前循环中, 跳过重复的值(与当前循环的第一个数字相同的数字)
            if (j == i || nums[j] != nums[j - 1]) {
                List<Integer> co = new ArrayList<Integer>(list);
                co.add(nums[j]);
                helper(res, co, nums, j + 1);
            }
        }
    }
}

解法2

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        int pre = 0;
        for(int i = 0; i < nums.length; i++) {
            int start = 0;
            if(i > 0 && nums[i] == nums[i-1])
                start = pre;
            pre = res.size();
            for(int j = start, size = res.size(); j <size; j++) {
                List<Integer> list = new ArrayList<Integer>(res.get(j));
                list.add(nums[i]);
                res.add(list);
            }
        }
        return res;
    }
}
⚠️ **GitHub.com Fallback** ⚠️