Hints — p38 Subsets

Hint 1. “All 2^n subsets”. You have multiple algorithm choices. Try one.

Hint 2. Easiest framing: iterative growth. Start with [[]]. For each new element, double the result by appending it to every existing subset:

result = [[]]
for x in nums:
    result = result + [s + [x] for s in result]

Hint 3. Backtracking framing: it’s like p37, but snapshot at EVERY node, not just at leaves. Every prefix is a valid subset.

def backtrack(start, path):
    result.append(path[:])               # snapshot here
    for i in range(start, n):
        path.append(nums[i]); backtrack(i+1); path.pop()

Hint 4. Include/exclude framing: at each index, branch into “skip nums[i]” and “take nums[i]”:

def backtrack(i, path):
    if i == n: result.append(path[:]); return
    backtrack(i+1, path)              # exclude
    path.append(nums[i]); backtrack(i+1, path); path.pop()   # include

Hint 5. For LC 90 (duplicates), sort + at each level skip equal siblings:

for i in range(start, n):
    if i > start and nums[i] == nums[i-1]: continue
    ...

Note i > start, NOT i > 0.

If still stuck: see solution.py.