We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subsets II

Number: 90

Difficulty: Medium

Paid? No

Companies: Microsoft, Google, Amazon, Bloomberg, Meta, Walmart Labs, Yahoo, Adobe, Apple, TikTok, Flipkart

Problem Description

Given an integer array that may contain duplicates, return all possible subsets (the power set) without including duplicate subsets. The order of the subsets is not important.

Key Insights

  • Sort the array first so that duplicate elements are adjacent.
  • Use backtracking to generate all possible subsets.
  • Skip duplicate elements in the recursion to avoid forming duplicate subsets.
  • The use of sorted order and conditionally skipping elements is the trick to handle duplicates.

Space and Time Complexity

Time Complexity: O(2^n * n) since each subset creation may take O(n) in the worst case.
Space Complexity: O(2^n * n) for storing the subsets, plus O(n) for recursion stack.

Solution

The solution uses a backtracking technique that builds subsets incrementally. The input array is first sorted to bring duplicates together. During recursion, if the current element is the same as the previous one and it has not been used in the current recursion path, it is skipped to prevent duplicate subsets. This ensures that each subset is unique. The algorithm stores each valid subset by copying the current subset state into the result list.

Code Solutions

def subsetsWithDup(nums):
    # Sort the numbers to handle duplicates
    nums.sort()
    result = []  # To store all subsets
    subset = []  # Current subset being built

    def backtrack(start):
        # Append a copy of the current subset to the result
        result.append(list(subset))
        # Iterate over possible elements to include
        for i in range(start, len(nums)):
            # If the current element is a duplicate and not at the start of this loop, skip it
            if i > start and nums[i] == nums[i - 1]:
                continue
            # Include current element into the subset
            subset.append(nums[i])
            # Recurse with next start index
            backtrack(i + 1)
            # Backtrack and remove the last element added
            subset.pop()
    
    backtrack(0)
    return result

# Example usage:
print(subsetsWithDup([1, 2, 2]))
← Back to All Questions