[LeetCode] 90. Subsets II

Posted on | In

Problem

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Explanation 1

  1. We can use backtracking to solve this problem. Because the result cannot contain duplicate subsets, this is similar to 40. Combination Sum II, we first need to sort the input array, then do the backtracking.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    void helper(int[] nums, int start, List<List<Integer>> res, List<Integer> cur) {
        res.add(new ArrayList<>(cur));

        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[i] == nums[i-1]) continue;
            cur.add(nums[i]);
            helper(nums, i+1, res, cur);
            cur.remove(cur.size()-1);
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        List<Integer> cur = new ArrayList<>();
        helper(nums, 0, res, cur);
        return res;
    }
}

Explanation 2

  1. We can also improve base on the second solution of 78. Subsets. Either choose the current elementt or not choose the current element, and we add one more parameter to the helper function taken to record if the current state we choose or not choose. Also, we need to sort the input array before we start. For example, input array is [1, 2, 2'].

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
                                     +------->" "
                     +---->" "+--+
                     |           +------->"2'" (ignore b/c taken==false && 2'==2)
      +------>" "+---+
      |              +---->"2"+--+------->"2"
 " "+-+                          |
      |                          +-------->"22'"
      |
      |                           +----->"1"
      +              +---->"1"+---+
       ------>"1"+---+            +----->"12'" (ignore b/c taken==false && 2'==2)
                     |
                     +---->"12"+---+----->"12"
                                   |
                                   +----->"122'"

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    void helper(int[] nums, int start, List<List<Integer>> res, List<Integer> cur, boolean taken) {
        if (start == nums.length) {
            res.add(new ArrayList<>(cur));
            return;
        }
        helper(nums, start+1, res, cur, false);

        if (taken == false && nums[start] == nums[start-1]) {
            return;
        }

        cur.add(nums[start]);
        helper(nums, start+1, res, cur, true);
        cur.remove(cur.size()-1);
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        List<Integer> cur = new ArrayList<>();
        helper(nums, 0, res, cur, true);
        return res;
    }
}