Subsets II medium

Problem Statement

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,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2

Input: nums = [0] Output: [[],[0]]

Steps

1. Sort the input array: Sorting allows us to easily identify and skip duplicate subsets later.

2. Backtracking Algorithm: We use a backtracking approach to explore all possible combinations. The core idea is:

   • For each element in the sorted array, we have two choices: include it in the current subset or not.
   • We recursively explore both choices.
   • When we reach the end of the array, we have a complete subset, which we add to the result.

3. Handling Duplicates: The crucial part is handling duplicates. To avoid duplicate subsets, we only consider including an element if it's different from the previous element or if we're already including the previous element in the current subset.

Explanation

The backtracking algorithm systematically explores all possible combinations of elements. Sorting the input ensures that we encounter duplicate elements consecutively. The condition i > 0 and nums[i] == nums[i - 1] and i not in subset_index prevents duplicate subsets from being generated. If a duplicate element is encountered and the previous element is not already in the subset, then we skip adding the duplicate element to avoid duplicate subsets.

Code

def subsetsWithDup(nums):
    """
    Finds all unique subsets of a given array with possible duplicates.

    Args:
        nums: A list of integers.

    Returns:
        A list of lists, where each inner list is a unique subset.
    """
    nums.sort()  # Sort to handle duplicates easily
    result = []
    
    def backtrack(index, subset):
        result.append(subset.copy()) #add a copy to avoid modification by reference
        for i in range(index, len(nums)):
            #Skip duplicates unless the previous element is already in the subset.
            if i > 0 and nums[i] == nums[i - 1] and i not in subset_index:
                continue
            subset.append(i)
            subset_index.append(i)
            backtrack(i + 1, subset)
            subset.pop()
            subset_index.pop()

    subset = []
    subset_index = [] # Keep track of indices to handle duplicates efficiently
    backtrack(0, subset)
    return result

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the input array. This is because there are 2^N possible subsets, and for each subset, we might need to perform O(N) operations (copying, adding elements).

• Space Complexity: O(N * 2^N) in the worst case, as the result set could contain up to 2^N subsets, each of size up to N. The recursion stack also adds to the space complexity, but it's bounded by N in the worst case.