LeetCode 78: Subsets — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Backtracking | Array | Bit Manipulation | Recursion

The Problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets and can be returned in any order.

Approach

Uses backtracking to generate all subsets by recursively building each subset one element at a time. At each recursive call, we add the current subset to results, then explore all possibilities by including each remaining element and backtracking to explore other combinations.

Time: O(2^n * n) · Space: O(2^n * n)

Code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, subset):
            subsets.append(subset[:])  # Append a copy of the current subset

            for i in range(start, len(nums)):
                subset.append(nums[i])
                backtrack(i + 1, subset)
                subset.pop()  # Backtrack

        subsets = []
        backtrack(0, [])
        return subsets