Skip to content

78. Subsets

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Iterative (Expanding Subsets) Start with empty subset. For each number, create new subsets by copying existing ones and adding the current number. Doubles subset count with each iteration. \(O(n \times 2^n)\) \(O(2^n)\) for output
Recursive (Backtracking) Build subsets by making binary choices: include or exclude each element. Recursively explore both paths, adding current subset to result when reaching base case. \(O(n \times 2^n)\) \(O(2^n)\) for output

Implementation

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

        res = [[]]
        for n in nums:
            for _ in range(len(res)):
                subset = res.pop(0)

                # not include the current number "n"
                res.append(subset.copy())

                # include the current number "n"
                subset.append(n)
                res.append(
                    subset
                )

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

        subset = []

        def dfs(i) -> None:
            if i >= len(nums):
                res.append(subset.copy())
                print(subset)
                return

            subset.append(nums[i])
            dfs(i+1)

            subset.pop()
            dfs(i+1)

        dfs(0)
        return res