Subsets (Power Set)
The Subsets (power set) problem asks for all possible subsets of an integer array of unique elements, with no duplicate subsets.
Two branches for every element — leave it out, or take it. The leaves of that tree are all 2^N subsets.
READY
Nums
1
2
3
Subsets
0 / 8
Nothing decided yet. 8 subsets to find.
Next
Leave 1 out.
N
Intuition
Think of it as a series of decisions for each element: Include it in the current subset, or Exclude it.
If you have [1, 2, 3], for '1' you say Yes or No. Then for '2', you say Yes or No. This forms a binary decision tree.
Concept
Key Concepts:
- Backtracking: Explore one branch (e.g., include element), then backtrack to explore the other (exclude element).
- Decision Tree: At each step, we branch into two paths.
- Power Set: A set of size N has 2^N subsets.
How it Works
- Start with an empty subset [].
- For each element in the input array:
- Include the element: Add it to the current path, move to next index.
- Exclude the element: Don't add it, move to next index.
- Base Case: When index equals array length, add current path to results.
Step-by-Step Breakdown
Input: [1, 2]
- Start: []
- Index 0 (Element 1):
- - Include: [1] -> Recurse Index 1
- -- Index 1 (Element 2):
- --- Include: [1, 2] -> Done
- --- Exclude: [1] -> Done
- - Exclude: [] -> Recurse Index 1
- -- Index 1 (Element 2):
- --- Include: [2] -> Done
- --- Exclude: [] -> Done
When to Use
- Generating all combinations/subsequences.
- Solving problems like "Knapsack" (brute force), "Subset Sum".
When NOT to Use
- When you only need the number of subsets (use math 2^N).
- When input size is large (N > 20) due to exponential complexity.
How to Identify
"Find all subsets", "Power Set", "Combinations of any length".
Applying for software engineering roles? Free, no sign-up: