Medium
Subsets
👶 The 5-Year-Old Summary
List ALL possible combinations from a set! Including empty set and the set itself. From [1,2,3], you get: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]!
🎮 Interactive Visualizer
Input: [1, 2, 3]
🧠The Brain Hack
Include or exclude each element! At each step, you have two choices: include the current number OR don't include it. 2^n subsets for n elements!
💻 The Clean Solution
def subsets(nums):
result = []
def backtrack(start, current):
# Every iteration is a valid subset!
result.append(current[:])
# Try adding each remaining number
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
# [1, 2, 3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]Time: O(n × 2^n)
Space: O(n)