Medium
Backtracking
Subsets
For each element, branch on include vs exclude.
Approach
Backtrack over indices: at each step record the current partial subset, then for each remaining element, include it, recurse, and undo. Because every element is independently in or out, you enumerate all 2ⁿ subsets exactly once.
Time complexity
O(n · 2ⁿ)
Space complexity
O(n) recursion
Common mistake
Producing duplicate subsets by not advancing the start index, or mutating the shared list without undoing.
See it run, step by step
Generate an interactive lesson for Subsets — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Subsets