Subsets
Given an array of distinct integers nums, return all possible subsets.
The solution set must not contain duplicate subsets. You may return the subsets in any order. The empty set ([]) is always a valid subset and should be included in the output.
Examples
Input: [2,4,3] Output: [[], [2], [4], [3], [2, 4], [2, 3], [4, 3], [2, 4, 3]] Input: [8] Output: [[], [8]]
We can use backtracking to solve the Subsets problem because the solution space, all possible combinations of elements forms a power set, which grows exponentially with the number of elements. For n elements, there are 2^n subsets. Backtracking is a natural fit because it allows us to systematically explore all combinations by including or excluding each element, without needing to generate all combinations manually.
Algorithm
Start from end (optional): Begin from the last index (len(nums) - 1) to index 0. (Can also start from 0 to n - 1.)
Backtracking function: Define a recursive function that takes the current index and a subset list as arguments.
Base case: If the index is out of bounds (idx < 0), add a copy of the current subset to the result.
Explore two choices: At each step:
- Include the current element and recurse.
- Exclude the current element and recurse.
Backtrack: Remove the last included element after exploring the include path so we can explore the exclude path cleanly.
from typing import List
def subsets(nums: List[int]) -> List[List[int]]:
res = []
def backtrack(idx, subset):
if idx < 0:
res.append(subset.copy())
return
subset.append(nums[idx])
backtrack(idx-1, subset)
subset.pop()
backtrack(idx-1, subset)
return
backtrack(len(nums)-1, [])
return resTime Complexity:O(2^n). Each of the n elements can be included or excluded → 2ⁿ combinations.
Space Complexity: O(n) for the recursion stack; O(2^n * n) for storing all subsets.