Exercise 1: Subsets 📦

Your Task

Given an array nums of unique integers, return all possible subsets of nums.

The solution set must not contain duplicate subsets
You may return the solution in any order

Examples

print(subsets([1, 2, 3]))
# Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

print(subsets([7]))
# Output: [[], [7]]

print(subsets([]))
# Output: [[]]

The Pattern

For each element, you have two choices:

Include it in the current subset
Exclude it

                    []
                   /   \
                 [1]    []
                /  \   /  \
            [1,2] [1] [2] []
              |     |   |   |
           [1,2,3] [1,3] [2,3] [3]

Hints

Starter Code

def subsets(nums):
    # Your code here
    pass

# Test your function:
print(subsets([1, 2, 3]))
# Expected: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

print(subsets([7]))
# Expected: [[], [7]]

Bonus Challenge 🌟

Solve it using a for loop instead of the exclude branch. (Iterate from start to end, pick one, recurse with start = i + 1, then backtrack.)

def subsets_loop(nums):
    result = []
    def build(path, start):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            build(path, i + 1)
            path.pop()
    build([], 0)
    return result

Both approaches work — the first is closer to the "choose / don't choose" pattern; the second is often shorter to write!

Permutations