Subsets¶
Also known as: Backtracking (Subsets), Power Set, Combinations
For each element, you make one decision — take it or leave it — and explore both branches. The recursion tree is the answer set. Backtracking simply means undoing your choice on the way back up, so the next branch starts clean.
Before you start¶
What 'solved properly' looks like
Target: O(2^n × n) for subsets; O(C(n,k) × k) for fixed-size combinations. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You walk through the input, and at each element you branch: either include it or exclude it. When you reach the end, you record the current combination. The "backtracking" part happens on the way back up — you undo the include choice so the next branch starts from a clean slate. This is the simplest form of exhaustive search, and it's the foundation of every harder pattern that follows.
Why it matters: It's the first pattern where the answer is "try everything, but intelligently prune," and it's the direct ancestor of dynamic programming (DP is this, with a memory to avoid recomputing branches). Letter Combinations and Combination Sum are real interview questions, and the decision-tree thinking you build here carries into every later exhaustive-search pattern.
When to reach for it¶
Reach for it when a problem asks for "all subsets", "all combinations", "every way to reach a sum", or uses a choose-or-don't-choose structure. If the answer is a list of lists, subsets or backtracking is probably the tool.
When not to use it
It's exponential by nature — if n is large, this is the wrong pattern and you're probably looking at DP or greedy. Duplicates in the input need explicit handling (sort first, then skip equal siblings at the same depth) or you'll emit the same subset twice. And don't confuse it with permutations: here, order within a subset doesn't matter.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Subsets | LeetCode | Medium | 20 mins | teaching |
| 2 | Letter Combinations of a Phone Number | LeetCode | Medium | 20 mins | teaching |
| 3 | Combination Sum | LeetCode | Medium | 25 mins | consolidation |
| 4 | Subsets II | LeetCode | Medium | 25 mins | consolidation |
| 5 | Palindrome Partitioning | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Palindrome Partitioning cleanly in one sitting — exploring all ways to split a string into palindromic substrings — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.