algoadvance

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.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Example 2:

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

Clarifying Questions

  1. Q: Are the elements in the array guaranteed to be unique? A: Yes, all elements in the array are unique.

  2. Q: Can the elements of the subsets be in any order? A: Yes, the elements of the subsets can be in any order.

  3. Q: What is the maximum length of the input array? A: The problem does not specify a maximum length, but we can assume it to be within a manageable range for solution coding purposes.

Strategy

We’ll solve this problem using backtracking. The idea is to build the subsets incrementally and explore all possibilities:

  1. Sort the input array (even though elements are unique - this helps with ordered combinations).
  2. Use a recursive helper function that adds the current list of elements (existent subset) to the result set.
  3. The helper function will then iterate over the remaining elements, adding each to the current subset, and recursively calling itself to continue the process with the next elements.
  4. Backtrack by removing the last added element and moving on to the next.

Code

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    result = []
    
    def backtrack(start, path):
        # Add the current subset (path) to the result list
        result.append(path[:])
        
        for i in range(start, len(nums)):
            # Include nums[i] in the current subset
            path.append(nums[i])
            # Recur with the next element
            backtrack(i + 1, path)
            # Backtrack: remove the last element
            path.pop()
    
    # initiate the backtracking with an empty path
    backtrack(0, [])
    return result

# Example usage:
# nums = [1, 2, 3]
# print(subsets(nums))

Time Complexity

The time complexity of generating all subsets is (O(2^n \cdot n)):

Hence, the overall time complexity is (O(n \cdot 2^n)).

This approach ensures we systematically explore all combinations and backtrack correctly to generate all possible subsets.

Try our interview co-pilot at AlgoAdvance.com