Subsets II

Leetcode Link

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:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know

Subsets II

Solution

Implementation

Ready to land your dream job?

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

Recommended Readings