What it is
Counting questions ask "how many" rather than "which one" or "what is the value of" — how many combinations reach a target, how many times a value repeats, how many subsequences share a property. The trap is that "how many" sounds like it invites brute-force enumeration, but the intended solutions almost always avoid ever listing the things being counted: a running tally derived from a vote/majority argument, a dynamic-programming table where each cell holds a count rather than a best value, or a count carried alongside a length in a DP state so you get "how many" and "how long" from the same pass.
When it applies
- The answer is a single number describing how many items, combinations, or subsequences satisfy a condition, and the naive approach is to generate and count every one of them explicitly.
- The condition composes (a combination's validity is built from smaller sub-combinations), which usually means a DP table can accumulate counts bottom-up instead of enumerating top-down.
- The input guarantees something structural (a majority element exists, values are bounded) that lets a clever pass replace an exhaustive one.
- If instead you need to reconstruct or return one specific instance of the thing being counted (not just how many), you likely need the underlying search or DP anyway, but with a traceback step added — counting alone doesn't require it.
Tells in the problem
- "Count how many combinations/subsequences/ways" reach or satisfy some target — a hint that a DP array indexed by the target (or by length) accumulates counts rather than a single best value.
- "Order does not matter" for combinations that use repeated elements — a hint to iterate the choices in a fixed outer order (coin types, not amounts) to avoid counting the same combination twice.
- A guarantee like "a majority element always exists" — this specific guarantee licenses an O(1)-space counting trick (a running candidate and a vote counter) instead of a hash map.
- "Count how many subsequences achieve the longest length," layering a count on top of an optimization — a hint to track two values per state (best length so far, and how many ways reach that length) instead of one.
- Distinct index sets counted separately even when the values look identical — a reminder that you're counting positions, not counting distinct values.
The classic mistake
Iterating choices in the wrong order (amounts on the outside, coins on the inside) so that the same combination gets counted once per ordering of its parts, inflating a "combinations" answer into what is really a "permutations" answer, or vice versa when the question wanted permutations and got combinations. This happens because the recurrence for "ways to reach X" looks almost identical whether order matters or not — the only difference is which loop is on the outside — so it's easy to write a correct-looking DP that answers a subtly different question than the one asked. Before coding, restate in your own words whether [2,3] and [3,2] should count once or twice, and let that answer decide the loop order, rather than choosing the loop order first and hoping it matches.
Questions to start with
- Majority Element — the guarantee that a majority value exists licenses a single running-tally pass instead of a hash map of counts.
- Coin Change II — the canonical combinations-not-permutations counting DP, where loop order is the whole ballgame.
- Number of Longest Increasing Subsequence — layers a count on top of an optimization, tracking both the best length and how many subsequences reach it.