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

Solution

This question is an advanced version of Subsets, the only difference is that the input may contain duplicate elements. So we can use the same approach as in Subsets to find the subsets of nums. However, we still need to deduplicate the repeated elements. In Deduplication we learned that we can deduplicate by sorting the candidates and avoiding using a duplicate candidate that we have not used previously, we will do the same here.

We wish to fill in the logics for backtracking1 template.

  • is_leaf: all the paths is a subset of nums
  • get_edges: the potential edges are the numbers from nums[start_index:] or an empty edge that concludes the subset
  • is_valid: check whether the candidate nums[i] is the first appearance of that element in the current function call, that is, i > start_index and nums[i] == nums[i-1] is true when nums[i] is a duplicate, and false otherwise.

Since at every node, a special "edge" is to "close" the subset, we can add a copy of path to ans regardless of the value of other states. Then, when we get_edges we can consider only the numbers from nums[start_index:], as we have visited nums[0:start_index].

Implementation

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    def dfs(start_index, path):
        ans.append(path[:]) # add a copy of the path to the result
        for i in range(start_index, len(nums)):
            # prune if needed
            if i > start_index and nums[i] == nums[i-1]:    # avoid duplicates
                continue
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()
            
    ans = []
    nums.sort()
    dfs(0, [])
    return ans

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More