Subsets

Problem

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

Example 2:

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

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

Solution

Approach: Backtracking

The key insight is to build subsets by deciding for each element whether to include it or not. Use backtracking to explore both choices.

Implementation

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(start, path):
            # Add current subset to result
            result.append(path[:])

            # Try adding each remaining element
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()

        backtrack(0, [])
        return result

Iterative Approach:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = [[]]

        for num in nums:
            # Add num to all existing subsets
            result += [subset + [num] for subset in result]

        return result

Complexity Analysis

Time Complexity: O(n * 2^n), where n is the length of nums. There are 2^n subsets and each takes O(n) to copy.
Space Complexity: O(n) for recursion depth (not counting output).

Key Insights

Power Set Size: For n elements, there are 2^n subsets (each element can be included or excluded).
Backtracking Pattern: At each step, we decide whether to include current element, then recurse for remaining elements.
Subset Building: We add the current path to results at each recursive call, not just at base case.
Iterative Growth: The iterative approach builds subsets incrementally - for each new element, double the subsets by adding it to existing ones.
No Duplicates: Since all elements are unique and we process each element once, no duplicate subsets are generated.