90. Subsets II
Problem Description
The task is to return all possible subsets (also known as the power set) of a given integer array nums
, which may contain duplicates. The important constraint is that the solution set must not include duplicate subsets. These subsets can be returned in any order. A subset is a set containing elements that are all found in another set, which in this case is the array nums
. The power set is the set of all subsets including the empty set and the set itself.
For example, if nums
is [1,2,2]
, the possible unique subsets without considering order are:
- [] - [1] - [2] - [1,2] - [2,2] - [1,2,2]
The challenge here is to ensure that while generating the subsets, duplicates are not created.
Flowchart Walkthrough
Let's use the algorithm flowchart to analyze Leetcode problem 90, Subsets II, with the goal of determining the appropriate use of the backtracking pattern. Follow the Flowchart link for the decision map we'll navigate through:
Step-by-step Walkthrough:
-
Is it a graph?
- Answer: No. The problem does not involve representing relationships between nodes and edges. Subsets generation is a combinatorial problem.
-
Need to solve for kth smallest/largest?
- Answer: No. The problem is about generating all unique combinations, not finding a specific ordered element.
-
Involves Linked Lists?
- Answer: No. The problem is based on array manipulation.
-
Does the problem have small constraints?
- Answer: Yes. Although it involves generating subsets, which can exponentially grow, the input size itself is usually small enough to consider brute force or backtracking feasible.
-
Brute force / Backtracking?
- Answer: Yes. To generate all possible unique subsets, considering the presence of duplicates and the need for uniqueness, backtracking is particularly suitable. Backtracking allows us to explore each possibility, backtrack on our choices, and prevent duplicate entries effectively.
Conclusion: The flowchart clearly guides us to the necessity of using a backtracking approach for solving the Subsets II problem effectively, further substantiated by the systematic exclusions of alternative strategies based on the specific problem's characteristics and requirements.
Intuition
The core idea to avoid duplicates in the subsets is to sort the array nums
. Sorting brings identical elements next to each other, making it easier to avoid duplicates when constructing the subsets.
The solution uses Depth-First Search (DFS) to explore all the possible subsets. The process starts with an empty subset, and at each level, it includes the next number from the array into the current subset, then recursively continues to add the remaining numbers to form new subsets. This is done until all numbers have been considered. After each number is processed for a given subset, it is removed again (this operation is also known as backtracking), and the next number is tried.
To ensure no duplicated subsets are generated, there are two conditions:
-
Sort the Numbers: As mentioned, we start by sorting the array to bring duplicates together.
-
Skip over duplicates: While generating subsets, if the current element is the same as the previous element and the previous element was not included in the current subset being generated (checked by
i != u
), it is skipped to avoid creating a subset that has already been created.
This way, the dfs
function systematically constructs all subsets, but avoids any repeats, ensuring that the power set it returns is free from duplicate subsets.
Learn more about Backtracking patterns.
Solution Approach
The implementation of the solution uses recursion to generate the subsets and backtracking to make sure all possible subsets are considered. Here's how the implementation works, with reference to the given Python code above:
-
Sort the Array: The first thing the solution does is to sort
nums
. This is crucial because it ensures that duplicates are adjacent and can be easily skipped when generating subsets.nums.sort()
-
Depth-First Search (DFS): The
dfs
function is then defined. DFS is a common algorithm for exploring all the possible configurations of a given problem. In this case, it's used to generate all possible subsets by making a series of choices (to include or not include an element in the current subset). -
Recursive Exploration: Inside
dfs
, the current subsett
is first included in the answer setans
. This represents the choice of not including any more elements in the current subset.ans.append(t[:])
-
Iterative Inclusion: The function then iterates through the remaining numbers starting from index
u
. If the number at the current index is the same as the one before it and it's not the first iteration of the loop (checked byi != u
), it skips adding this number to avoid duplicates.for i in range(u, len(nums)): if i != u and nums[i] == nums[i - 1]: continue t.append(nums[i]) dfs(i + 1, t) t.pop()
t.append(nums[i])
adds the current number to the subset.- A recursive call
dfs(i + 1, t)
is made to consider the next number in the array. The indexi + 1
ensures that the function does not consider the current number again, thus moving forward in the array. t.pop()
is the backtracking step, which removes the last added number from the subset, allowing the function to consider other possibilities after returning from the recursive call.
-
Global Answer Set: An empty list
ans
is initialized outside thedfs
function. As the subsets are created, they are added toans
. Sinceans
is defined outside the scope of thedfs
function, it retains all the solutions across recursive calls.ans = []
-
Kick Start the DFS: The
dfs
function is initially called with the starting index0
and an empty subset[]
to start the exploration.dfs(0, [])
At the end of the execution, the global ans
contains all the subsets without duplicates, which is then returned as the final result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach using the array [2,1,2]
.
-
Sort the Array: First, sort the array to become
[1,2,2]
. Sorting ensures any duplicates are next to each other which helps later in the process to avoid duplicate subsets. -
Depth-First Search (DFS): We define a
dfs
function that will be used to explore possible subsets. -
Recursive Exploration: The exploration starts with an empty subset
[]
. This subset is immediately added to the answer setans
because it is a valid subset (the empty set). -
Iterative Inclusion: For the first call to
dfs
, we will look at each element starting with the first element of the sorted array.- Include the first element
[1]
. At this stage,dfs
is recursively called to consider the next number. - At the next level, we have
[1,2]
. We include it and then thedfs
explores further. - Now we have
[1,2,2]
, which is also included. - After considering each of these, we backtrack to
[1,2]
and remove the last element to reconsider our options. - Since the next element is the same as the previous (as we just removed it), the loop skips adding
[1,2]
again because it would be a duplicate.
- Include the first element
-
Backtracking: After the above steps, we backtrack to an empty subset
[]
and proceed to the next element:- The next element is
[2]
. We include it, and thendfs
is called recursively. - At the next level, the function sees another
2
. However, since the previous element is also2
, and we are not at the start of a new subset creation (checked byi != u
), the algorithm takes care not to include[2,2]
as this is already considered. This is where the duplicate gets skipped.
- The next element is
-
Global Answer Set: All the while, subsets like
[]
,[1]
,[1,2]
,[1,2,2]
, and[2]
are being added to the globalans
list. -
Complete Exploration: After the function explores all possibilities, the
ans
now contains, without duplicates:
- [] - [1] - [2] - [1,2] - [1,2,2]
- Return Results: Finally, the
dfs
has finished exploring, andans
with all the unique subsets is returned as the result.
This example demonstrates how the algorithm ensures all unique subsets of [2,1,2]
are found by methodically exploring all options while skipping over duplicates due to sorting and the extra conditional skip in the recursive loop.
Solution Implementation
1from typing import List
2
3class Solution:
4 def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
5 # Helper function to perform depth-first search
6 def depth_first_search(start_index, current_subset):
7 # Append a copy of the current subset to the answer list
8 result.append(current_subset[:])
9
10 # Iterate over the numbers starting from the current index
11 for index in range(start_index, len(nums)):
12 # Skip duplicates except for the start of a new subsection
13 if index != start_index and nums[index] == nums[index - 1]:
14 continue
15 # Include the current number and recurse
16 current_subset.append(nums[index])
17 depth_first_search(index + 1, current_subset)
18 # Backtrack by removing the last number added
19 current_subset.pop()
20
21 # This list will store all the subsets
22 result = []
23 # First sort the input array to handle duplicates
24 nums.sort()
25 # Start the recursive process with an empty subset
26 depth_first_search(0, [])
27 # Return the generated subsets
28 return result
29
30# Example usage:
31# sol = Solution()
32# print(sol.subsetsWithDup([1, 2, 2])) # Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
33
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6 // List to store the final subsets
7 private List<List<Integer>> subsets;
8
9 // The provided array of numbers, from which we will form subsets
10 private int[] numbers;
11
12 // Public method to find all subsets with duplicates
13 public List<List<Integer>> subsetsWithDup(int[] nums) {
14 subsets = new ArrayList<>(); // Initialize the subsets list
15 Arrays.sort(nums); // Sort the array to handle duplicates
16 this.numbers = nums; // Store the sorted array in the numbers variable
17 backtrack(0, new ArrayList<>()); // Start the backtrack algorithm
18 return subsets; // Return the list of subsets
19 }
20
21 // Helper method to perform the backtrack algorithm
22 private void backtrack(int index, List<Integer> currentSubset) {
23 // Add a new subset to the answer list, which is a copy of the current subset
24 subsets.add(new ArrayList<>(currentSubset));
25
26 // Iterate through the numbers starting from index
27 for (int i = index; i < numbers.length; ++i) {
28 // Skip duplicates: check if the current element is the same as the previous one
29 if (i != index && numbers[i] == numbers[i - 1]) {
30 continue; // If it's a duplicate, skip it
31 }
32
33 // Include the current element in the subset
34 currentSubset.add(numbers[i]);
35
36 // Recursively call backtrack for the next elements
37 backtrack(i + 1, currentSubset);
38
39 // Exclude the current element from the subset (backtrack step)
40 currentSubset.remove(currentSubset.size() - 1);
41 }
42 }
43}
44
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to generate all possible subsets with duplicates
7 std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
8 // Sort the numbers to handle duplicates easily
9 std::sort(nums.begin(), nums.end());
10
11 // This will be our result list of subsets
12 std::vector<std::vector<int>> subsets;
13
14 // Temporary list to build each subset
15 std::vector<int> tempSubset;
16
17 // Start the depth-first search from the first index
18 depthFirstSearch(0, tempSubset, nums, subsets);
19
20 return subsets;
21 }
22
23private:
24 // Recursive DFS function to explore all subsets
25 // 'index' is the current position in 'nums' array
26 void depthFirstSearch(int index, std::vector<int>& tempSubset, std::vector<int>& nums, std::vector<std::vector<int>>& subsets) {
27 // Add the current subset to the list of subsets
28 subsets.push_back(tempSubset);
29
30 // Iterate through the array starting from the 'index'
31 for (int i = index; i < nums.size(); ++i) {
32 // Skip the current number if it's the same as the previous one at the same tree depth
33 if (i != index && nums[i] == nums[i - 1]) continue;
34
35 // Include the current number in the subset
36 tempSubset.push_back(nums[i]);
37
38 // Continue searching further with the current number included
39 depthFirstSearch(i + 1, tempSubset, nums, subsets);
40
41 // Exclude the current number before going to the next iteration
42 tempSubset.pop_back();
43 }
44 }
45};
46
1function subsetsWithDup(nums: number[]): number[][] {
2 // Sort the array to handle duplicates.
3 nums.sort((a, b) => a - b);
4 const length = nums.length;
5 // Temporary array to hold intermediate solutions.
6 const temp: number[] = [];
7 // Resulting array of subsets.
8 const result: number[][] = [];
9 // Depth-first search function to explore subsets.
10 const backtrack = (index: number) => {
11 // If the end of the array is reached, add the current subset to the result.
12 if (index === length) {
13 result.push([...temp]);
14 return;
15 }
16 // Include the current number in the subset.
17 temp.push(nums[index]);
18 backtrack(index + 1); // Move to the next number.
19
20 // Remove the current number and skip all duplicates to prevent duplicate subsets.
21 const lastNumber = temp.pop();
22 while (index < length && nums[index] === lastNumber) {
23 index++;
24 }
25 backtrack(index);
26 };
27
28 // Start the backtracking with the first index of the array.
29 backtrack(0);
30 // Return all the subsets when done.
31 return result;
32}
33
Time and Space Complexity
The given Python code defines a method subsetsWithDup
that finds all possible subsets of a given set of numbers that might contain duplicates. To avoid duplicate subsets, the algorithm sorts the array and skips over duplicates during the depth-first search (DFS).
Time Complexity:
The time complexity of this algorithm can be analyzed based on the number of recursive calls and the operations performed on each call.
-
The function
dfs
is called recursively, at most, once for every element starting from the current indexu
. In the worst case, this means potentially callingdfs
for each subset ofnums
. -
Since
nums
hasn
elements, there are2^n
possible subsets including the empty subset. -
However, because the list is sorted and the algorithm skips duplicate elements within the same recursive level, the number of recursive calls may be less than
2^n
. -
The
append
andpop
methods of a list run inO(1)
time.
Therefore, the time complexity of the algorithm is essentially bounded by the number of recursive calls and is O(2^n)
in the worst case, when all elements are unique.
Space Complexity:
The space complexity is considered based on the space used by the recursion stack and the space needed to store the subsets (ans
).
-
The maximum depth of the recursive call stack is
n
, which is the length ofnums
. Each recursive call uses space for local variables, which isO(n)
space in the stack at most. -
The list
ans
will eventually contain all subsets, and thus, it will have2^n
elements, considering each subset as an element. However, the total space taken by all subsets combined is also considerable as each of the2^n
subsets could have up ton
elements. This effectively adds up toO(n * 2^n)
space.
Considering these factors, the space complexity of the code can be defined as O(n * 2^n)
because the space used by the algorithm is proportional to the number of subsets generated, and each subset at most can have n
elements.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
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
Want a Structured Path to Master System Design Too? Donāt Miss This!