dsa / dsa-sliding-window
24 mins
DSA Module 7: Backtracking & Power Set Generation
Why This Matters: Backtracking systematically searches decision trees by building solutions and abandoning invalid paths.
## Choose-Explore-Undo Backtracking Pattern
Generating all $2^N$ subsets using recursive backtracking.
```python
def subsets(nums: list[int]) -> list[list[int]]:
res = []
def backtrack(index, path):
res.append(list(path))
for i in range(index, len(nums)):
path.append(nums[i]) # 1. Choose
backtrack(i + 1, path) # 2. Explore
path.pop() # 3. Undo (Backtrack)
backtrack(0, [])
return res
```
MENTAL MODEL & MEMORY LAYOUT
BACKTRACKING DECISION TREE:
[]
/ | \
[1] [2] [3]
/ \
[1,2] [1,3] COMMON PITFALLS TO AVOID
- Forgetting to pop/undo choice `path.pop()` before returning to parent caller frame.
Power Set Backtracking
# Choose item -> Recurse deeper -> Pop item to undo state
Generates all 2^N subsets of a set using choose-explore-undo pattern.
CONCEPT MASTERY CHECKPOINT
How many total subsets exist for a set of size N?
NEXT RECOMMENDED LESSON
DSA Module 8: Binary Search & Search Spaces
Challenge: Return count of total subsets for set of size N.