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 ofnums
get_edges
: the potential edges are the numbers fromnums[start_index:]
or an empty edge that concludes the subsetis_valid
: check whether the candidatenums[i]
is the first appearance of that element in the current function call, that is,i > start_index and nums[i] == nums[i-1]
istrue
whennums[i]
is a duplicate, andfalse
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 EvaluatorWhat'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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!