Q73: Subsets (Power Set). - DSA Patterns (Multi-Lang)

In Simple Words: At each index, make binary decision: either include nums[i] or exclude nums[i]. When index reaches $N$, snapshot current subset.

Time: $O(N \cdot 2^N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def subsets(nums: list[int]) -> list[list[int]]:
    res = []
    subset = []
    def dfs(i):
        if i >= len(nums):
            res.append(subset.copy())
            return
        # Decision to include nums[i]
        subset.append(nums[i])
        dfs(i + 1)
        # Decision to NOT include nums[i]
        subset.pop()
        dfs(i + 1)
    dfs(0)
    return res