90. Subsets II

MediumBit ManipulationArrayBacktracking
Leetcode Link

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]
3- [2]
4- [1,2]
5- [2,2]
6- [1,2,2]

The challenge here is to ensure that while generating the subsets, duplicates are not created.

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:

  1. Sort the Numbers: As mentioned, we start by sorting the array to bring duplicates together.

  2. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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:

  1. 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.

    1nums.sort()
  2. 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).

  3. Recursive Exploration: Inside dfs, the current subset t is first included in the answer set ans. This represents the choice of not including any more elements in the current subset.

    1ans.append(t[:])
  4. 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 by i != u), it skips adding this number to avoid duplicates.

    1for i in range(u, len(nums)):
    2    if i != u and nums[i] == nums[i - 1]:
    3        continue
    4    t.append(nums[i])
    5    dfs(i + 1, t)
    6    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 index i + 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.
  5. Global Answer Set: An empty list ans is initialized outside the dfs function. As the subsets are created, they are added to ans. Since ans is defined outside the scope of the dfs function, it retains all the solutions across recursive calls.

    1ans = []
  6. Kick Start the DFS: The dfs function is initially called with the starting index 0 and an empty subset [] to start the exploration.

    1dfs(0, [])

At the end of the execution, the global ans contains all the subsets without duplicates, which is then returned as the final result.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the array [2,1,2].

  1. 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.

  2. Depth-First Search (DFS): We define a dfs function that will be used to explore possible subsets.

  3. Recursive Exploration: The exploration starts with an empty subset []. This subset is immediately added to the answer set ans because it is a valid subset (the empty set).

  4. 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 the dfs 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.
  5. 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 then dfs is called recursively.
    • At the next level, the function sees another 2. However, since the previous element is also 2, and we are not at the start of a new subset creation (checked by i != u), the algorithm takes care not to include [2,2] as this is already considered. This is where the duplicate gets skipped.
  6. Global Answer Set: All the while, subsets like [], [1], [1,2], [1,2,2], and [2] are being added to the global ans list.

  7. Complete Exploration: After the function explores all possibilities, the ans now contains, without duplicates:

1- []
2- [1]
3- [2]
4- [1,2]
5- [1,2,2]
  1. Return Results: Finally, the dfs has finished exploring, and ans 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.

Not Sure What to Study? Take the 2-min Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

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.

  1. The function dfs is called recursively, at most, once for every element starting from the current index u. In the worst case, this means potentially calling dfs for each subset of nums.

  2. Since nums has n elements, there are 2^n possible subsets including the empty subset.

  3. 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.

  4. The append and pop methods of a list run in O(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).

  1. The maximum depth of the recursive call stack is n, which is the length of nums. Each recursive call uses space for local variables, which is O(n) space in the stack at most.

  2. The list ans will eventually contain all subsets, and thus, it will have 2^n elements, considering each subset as an element. However, the total space taken by all subsets combined is also considerable as each of the 2^n subsets could have up to n elements. This effectively adds up to O(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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫