← Backtracking

Micro-Drill #268 — Subsets (include/exclude)

Backtracking Target: 15s

At each index, branch into include or exclude. Generates all 2^n subsets. Alternative: iterative bit-mask approach.

def subsets(nums):
    res = []
    def bt(i, path):
        if i == len(nums):
            res.append(path[:])
            return
        bt(i+1, path)             # exclude
        path.append(nums[i])
        bt(i+1, path)             # include
        path.pop()
    bt(0, [])
    return res

Type it from memory. Go.

Practice Problems

• 78. Subsets
• 90. Subsets II

Related Coding Drills

• Drill #50 — Generate all subsets Medium
• Drill #32 — Merge two sorted arrays Easy
• Drill #116 — Minimum Interval to Include Each Query Hard