Algorithms / Subsets Combinations Search
Least You Need to Know: Subsets, Combinations, and Choose/Skip Search
Subset and combination search usually depends on a **choose/skip** structure. The important distinction is that order does not matter, so the recursion should move forward through candidates instead of revisiting earlier positions.
The least you need to know
- Subset search often branches on include versus exclude for the current item.
- Combination search should avoid generating the same group in different orders.
- A start index or forward-only position is a common way to prevent duplicate combinations.
- When order does not matter, states should be described by which candidates remain, not by permutation order.
- Combination backtracking usually appends one choice, recurses on later candidates, then removes it.
Key notation
include / exclude
choose the current item or skip it
start index
first candidate allowed in this recursive call
combination
an unordered selection of items
Tiny worked example
- To list size-2 combinations from `[a,b,c]`, begin at index `0`.
- Choose `a`, recurse on later positions, and pair it with `b` and `c`.
- Then backtrack, skip `a`, and continue from `b`.
- Because recursion only moves forward, `{a,b}` and `{b,a}` are not both generated.
Common mistakes
- Students often accidentally generate permutations when the task only asks for combinations.
- Students often restart from index `0` after each choice and create duplicates.
- Students often forget that the empty subset is still a valid subset in many enumeration problems.
How to recognize this kind of problem
- The prompt asks for subsets, combinations, or unordered selections.
- The same chosen values should not appear again in a different order.
- A forward-only candidate index naturally matches the problem.
Next recommended lesson
Continue through this topic with Least You Need to Know: Suffix Ordering, Lexicographic Structure, and LCP Intuition.
Least You Need to Know: Suffix Ordering, Lexicographic Structure, and LCP IntuitionRelated lessons
Keep going with nearby lessons in the same topic.