Solution Explanation for Subsets II

The problem asks to find all unique subsets of a given integer array that may contain duplicate elements. The solution involves two main approaches: Depth-First Search (DFS) and Binary Enumeration. Both approaches require sorting the input array first to easily handle duplicates.

Approach 1: Sorting + DFS (Depth-First Search)

This approach uses recursion to explore all possible subsets.

Algorithm:

1. Sort the input array: Sorting allows us to easily identify and skip duplicate elements during the DFS traversal. This prevents generating duplicate subsets.

2. DFS Function (dfs(i)): This recursive function takes an index i as input, representing the current element being considered.

   • Base Case: If i reaches the end of the array, it means a complete subset has been formed. Add a copy of the current subset (t) to the result list (ans).

   • Recursive Steps:

     • Include the current element: Add nums[i] to the current subset (t). Recursively call dfs(i + 1) to explore subsets including this element. Then, remove nums[i] from t (backtracking).
     • Skip duplicate elements: Check if the next element nums[i+1] is the same as the current element nums[i]. If they are the same, increment i to skip consecutive duplicates. This is crucial for avoiding duplicate subsets. Recursively call dfs(i + 1) to explore subsets without including the current element (and its duplicates).

3. Initial Call: Call dfs(0) to start the process from the beginning of the sorted array.

Time Complexity: O(N * 2N), where N is the length of the input array. In the worst case (no duplicates), we generate all 2N subsets. The work done for each subset is proportional to N (adding elements to the subset).

Space Complexity: O(N). This is dominated by the recursion depth (the maximum depth of the recursion stack) and the space used by the temporary subset list t.

Approach 2: Sorting + Binary Enumeration

This approach uses bit manipulation to generate all possible subsets.

Algorithm:

1. Sort the input array: Same as in Approach 1, this helps eliminate duplicate subsets.

2. Binary Enumeration: Iterate through numbers from 0 to 2N - 1 (where N is the length of the input array). Each number represents a subset: The binary representation of the number indicates which elements are included in the subset (1 means include, 0 means exclude).

3. Subset Generation: For each number (mask), iterate through the bits. If the i-th bit is 1, add nums[i] to the current subset (t).

4. Duplicate Check: If the current element is the same as the previous element AND the previous element wasn't included in the subset, we skip adding the current element to avoid duplicates.

5. Add to Result: If a unique subset is generated, add it to the result list (ans).

Time Complexity: O(N * 2N). Similar to Approach 1, we iterate through 2N possible subsets, and for each subset, we perform work proportional to N.

Space Complexity: O(N). This is mainly due to the space used for storing the current subset t.

Code Examples (Python)

Approach 1 (DFS):

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = []
        t = []
 
        def dfs(i):
            if i == n:
                ans.append(t.copy())
                return
            t.append(nums[i])
            dfs(i + 1)
            t.pop()
            j = i + 1
            while j < n and nums[j] == nums[i]:
                j += 1
            dfs(j)
 
        dfs(0)
        return ans
 

Approach 2 (Binary Enumeration):

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = []
        for i in range(1 << n):
            subset = []
            for j in range(n):
                if (i >> j) & 1:
                    if not j or nums[j] != nums[j - 1] or (i >> (j - 1)) & 1:
                        subset.append(nums[j])
            ans.append(subset)
        return ans

Both approaches achieve the same result but have slightly different implementation styles. The DFS approach is often considered more intuitive for recursive problems, while the binary enumeration approach can be more concise for this specific problem. Choose the approach that you find more understandable and easier to maintain.