Link: 78. Subsets
Track: NeetCode150

Question

Restate the problem

Given an integer array nums containing distinct elements.
Return all possible subsets (the power set) of nums.

Q: Does return order matter?

Each subset can be in any order
Q: Does array have duplicate number?
No
Q: Do we include the empty subset []?
Yes

Method

Approach - Backtracking

DFS function is dfs(start, path):

start is the next index I’m allowed to choose from.
path is the current subset I’ve built.

At every call, the current path is already a valid subset, so I add a copy of it to the result.
Then I try all possible next elements i from start to the end:

choose nums[i]
recurse with start = i + 1
undo the choice (pop) to explore the next option.

Using i + 1 guarantees indices are strictly increasing, so we generate each combination once and avoid permutations like [2,1].

Complexity

Time Complexity: O( $n * 2^{n}$ )
- Subset: $2^{n}$
- Copy: $O (n)$
Space Complexity: O(n)

Edge Case

if nums = [], return [[]]

Code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        def dfs(start, path):
            # if start > n:
            #     return
 
            res.append(path[:])
            
            for idx in range(start, n):
                path.append(nums[idx])
                dfs(idx + 1, path)
                path.pop()
 
        dfs(0, [])
        return res

History

Jan-18-2026 Solved w bug, 1) boundary wrong 2)wrong time complexity

Notes

Explorer

0078.Subsets