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

Number: 78

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Bloomberg, Microsoft, TikTok, tcs, Coupang, Walmart Labs, Wix, Mastercard, Apple, Adobe, Yahoo, Uber, Goldman Sachs, Oracle, IBM

Problem Description

Given an integer array nums consisting of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. The order of the output does not matter.

Key Insights

  • The problem is equivalent to generating the power set of the given set.
  • A recursive backtracking approach can be used to explore both including and excluding each element.
  • Iterative (bit manipulation) solutions are also possible since there are 2^n subsets in total.
  • The maximum array length is small (up to 10), making exponential time solutions feasible.

Space and Time Complexity

Time Complexity: O(2^n * n) - There are 2^n subsets and creating each subset may take up to O(n) time. Space Complexity: O(2^n * n) - Space for storing all subsets. The recursion stack has a maximum depth of O(n).

Solution

We solve the problem using backtracking, where we decide for each element whether to include it in the current subset or not. We recursively build all subsets starting at an empty list and at each step appending the current subset to our result list. We can also use iterative bit manipulation but here we focus on the backtracking approach. This algorithm leverages recursion and a list to maintain the current state, leading to a clear and concise implementation.

Code Solutions

# Define the function to generate all subsets using backtracking.
def subsets(nums):
    # This list will store all the subsets
    result = []
    
    # Recursive helper function to generate subsets.
    def backtrack(start, current):
        # Append a copy of the current subset to the final result.
        result.append(current.copy())
        # Iterate over the possible next elements starting from index 'start'
        for i in range(start, len(nums)):
            # Include nums[i] in the current subset.
            current.append(nums[i])
            # Recurse with the next starting index.
            backtrack(i + 1, current)
            # Backtrack: remove the last element to explore other possibilities.
            current.pop()
    
    # Start the recursion with an empty path.
    backtrack(0, [])
    return result

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