78. Subsets
Summary
Given an integer array nums of unique elements, return all possible subsets (the power set).
Approach
Use backtracking.
[] -> [1], [2], [3] -> [1,2], [2,3] -> [1,2,3]
This backtracking function keeps track of the current index. Once the index reaches the end, the search stops.
Function
Initialization:
results
Function backtrack(comb, index):
results.append(list(comb)) // create a copy
If index is greater than len(nums) - 1:
return
For i in index..len(nums) - 1:
comb.append(nums[i])
backtrack(comb, i + 1)
comb.pop()
Complexity
Time Complexity: O(N * 2^N) because there are 2^N subsets, and copying each subset takes up to O(N).
Space Complexity: O(N) because the recursion stack grows to at most N.