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.
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
Worked example
- To list size-2 combinations from
[a,b,c], begin at index0. - Choose
a, recurse on later positions, and pair it withbandc. - Then backtrack, skip
a, and continue fromb. - 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
0after each choice and create duplicates. - Students often forget that the empty subset is still a valid subset in many enumeration problems.
How to recognize it
- 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.