Subsets – Solution & Complexity
Watch: Subsets with take-or-skip backtracking
Each number is either in a subset or not, so n numbers give 2ⁿ subsets. Backtracking walks that decision tree: at index i, take the number, recurse, pop it, then skip it and recurse. When i reaches the end, save a copy of the path. The iterative version starts from the empty set and doubles the list for each number. O(n · 2ⁿ) time, O(n) extra space besides the output.
Solution Walkthrough
Step 1: Understand the Goal
- Identify the required output and the state that changes.
- Use the examples to rule out tempting but incorrect interpretations.
Step 2: Choose the Core Pattern
- This problem is best exposed by Backtracking makes an include/exclude decision for each value.
- Maintain only the state needed for the next operation.
Step 3: Build the Algorithm
- Process each state once when possible.
- Record state before scheduling dependent work to avoid duplicates.
Step 4: Check Edge Cases
- Verify the smallest input, impossible cases, and repeated values where allowed.
- Keep output ordering deterministic.
Step 5: Final Solution and Complexity
- Time complexity is O(n*2^n).
- Space complexity is O(n*2^n).