Power Set / Subsets

LeetCode #78 [Medium]

Problem Statement

Given a set of distinct integers, return all possible subsets (the power set).

Example: Input: [1,2] → Output: [[], [1], [2], [1,2]]

Approach 1: Recursive Backtracking

Explanation: Decide for each element whether to include it in current subset and recurse.

Time Complexity: O(2ⁿ × n) (all subsets × copy time)

Space Complexity: O(n) (recursion stack)

function backtrack(index, current):
    if index == n:
        add current copy to result
        return
    // Include nums[index]
    backtrack(index+1, current + [nums[index]])
    // Exclude nums[index]
    backtrack(index+1, current)
backtrack(0, [])

💡 Think: At each step, decide whether to include the current element or not (recursion tree).

Approach 2: Iterative

Explanation: Start with empty subset, for each number, add it to all existing subsets.

Time Complexity: O(2ⁿ × n)

Space Complexity: O(2ⁿ × n)

result = [[]]
for num in nums:
    for subset in result.copy():
        result.append(subset + [num])
return result

💡 Think: Start with [[]] and for each number, duplicate subsets by adding that number.

Approach 3: Bit Manipulation

Explanation: Each subset corresponds to a bitmask of length n.

Time Complexity: O(2ⁿ × n)

Space Complexity: O(2ⁿ × n)

for mask in 0..2^n-1:
    subset = []
    for i in 0..n-1:
        if mask & (1 << i):
            subset.append(nums[i])
    add subset to result
return result

💡 Think: Treat each subset as a bitmask of length n, where 1 indicates inclusion.

Solve on LeetCode