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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Subsets

Difficulty: Medium

Problem Description

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Key Insights

  • The problem requires generating all possible combinations of a given set of unique integers.
  • Each element can either be included in a subset or excluded, leading to a binary choice for each element.
  • The total number of subsets for an array of length n is 2^n.
  • Backtracking or iterative methods can be used to explore all combinations.

Space and Time Complexity

Time Complexity: O(2^n)
Space Complexity: O(n) (for the recursion stack in backtracking)

Solution

To solve this problem, we can use a backtracking approach where we explore all possible combinations of the elements in the input array. At each step, we can choose to either include the current element in the subset or skip it. We will maintain a temporary list to store the current subset being formed. Once we have considered all elements, we add the current subset to the list of results. This approach efficiently generates all possible subsets.

Code Solutions

def subsets(nums):
    result = []
    
    def backtrack(start, path):
        # Add the current subset to the result
        result.append(path)
        for i in range(start, len(nums)):
            # Include nums[i] in the subset
            backtrack(i + 1, path + [nums[i]])
    
    backtrack(0, [])
    return result
← Back to All Questions