How to Solve Combinations with Restrictions
Solve restricted combination aptitude problems — cannot both, at least one from subset — with the complement trick and worked examples.
Expected Interview Answer
Combinations with restrictions — certain items forced in, forced out, or mutually exclusive — are solved by breaking the unrestricted nCr count into smaller independent cases based on the restriction, then adding or multiplying those cases, or by computing the complement of the forbidden cases from the total.
For “at least one of a specific subset must be chosen,” split into cases by exactly how many from that subset are included and sum the products of each case’s combinations, or use the complement: total unrestricted combinations minus the combinations that include none of the subset. For “two specific items cannot both be chosen,” compute the unrestricted total and subtract the cases where both are included together (fix both, choose the rest from what remains). For “if item A is chosen, item B must also be chosen,” it is often easiest to count the complement: total minus cases where A is chosen without B. Multi-condition problems combine these techniques by isolating each condition into an independent stage and multiplying, exactly as with committee subgroup quotas.
- The complement trick turns awkward “at least”/"cannot both" conditions into simple subtraction
- Splitting into cases-by-count handles “at least k from subset” cleanly
- Fixing forced pairs reduces multi-condition problems to smaller, independent nCr stages
AI Mentor Explanation
Selecting a 5-player fielding sub-unit from 10 available players, where two specific players who always clash on the field cannot both be selected, is solved by taking the unrestricted total 10C5 and subtracting the cases where both clashing players are included together — fix both, choose the remaining 3 from the other 8: 8C3. This complement approach — total minus the forbidden overlap — is the standard technique for any “these two cannot both appear” restriction in combination problems.
Worked example (two items cannot both be chosen)
Unrestricted total
- 10C4 = 210
Both X and Y together
- Fix X,Y; choose 2 from 8
- 8C2 = 28
Valid committees
- 210 − 28 = 182
Step-by-Step Explanation
Step 1
Identify the restriction type
"At least one," "cannot both," or “if A then B” each need a different technique.
Step 2
For “cannot both”: subtract the overlap
Total minus the cases where both forbidden items are chosen together.
Step 3
For “at least one/k from subset”: use complement or case-sum
Total minus zero-from-subset, or sum exact-count cases from k to the subset size.
Step 4
Verify with a smaller check
Sanity-check by computing a tiny version of the problem by hand.
What Interviewer Expects
- Correctly identifying which restriction technique applies to the wording
- Correct use of the complement for “cannot both” and “at least one” cases
- Correct case-splitting and summation for “at least k from a subset”
- A sanity check confirming the restricted count is smaller than the unrestricted total
Common Mistakes
- Adding instead of subtracting the forbidden overlap for “cannot both” problems
- Forgetting to sum ALL valid cases (e.g., missing the “exactly k+1” or “exactly k+2” case) for “at least k”
- Using the wrong reduced pool size after fixing forced-together items
- Not verifying the final answer is smaller than the unrestricted nCr total
Best Answer (HR Friendly)
“Restrictions are almost always handled by either subtracting a forbidden overlap from the unrestricted total, or by splitting into exact-count cases and adding them up. If two people cannot serve together, work out the unrestricted count, then subtract the cases where both are included. If at least one must come from a subset, it is usually fastest to subtract the “none from that subset” case from the total, unless summing exact-count cases is more direct.”
Follow-up Questions
- How would you solve this if three specific items were mutually exclusive in pairs?
- How does the technique change for “exactly k from the subset” versus “at least k”?
- How would you combine a “cannot both” restriction with a subgroup quota in the same problem?
- How would you verify a restricted-combination answer using a smaller test case?
MCQ Practice
1. A 4-person team is chosen from 9 people. Two specific people cannot both be on the team. How many valid teams?
Total 9C4 = 126. Both together: fix both, choose 2 from remaining 7 = 7C2 = 21. Valid = 126 − 21 = 105.
2. A 3-item selection is made from 8 items, where at least 1 must come from a specific set of 3. How many selections?
Total 8C3 = 56. None from the subset: choose all 3 from remaining 5 = 5C3 = 10. At least one = 56 − 10 = 46.
3. Which technique best solves “at least one of a required subset must be chosen”?
The complement — subtracting the case where none of the required subset is chosen — is the standard technique for “at least one.”
Flash Cards
How to solve “two items cannot both be chosen”? — Total unrestricted combinations minus the cases where both are chosen together.
How to solve “at least one from a subset”? — Total minus the case with zero items from that subset.
How to solve “at least k from a subset” generally? — Sum the exact-count cases from k up to the subset size.
How to sanity-check a restricted-combination answer? — Confirm it is smaller than the unrestricted nCr total, and test on a small example.