Count Legal Outfit Combinations
Reported by candidates from Duolingo's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Duolingo reported this one in September 2021, and it looks like a wardrobe puzzle until you read the constraints. Strip the clothing and it's counting independent sets in a small graph: items are nodes, illegal pairs are edges, and a legal outfit is a subset with no edge inside it. With at most 20 items, you can enumerate every subset with a bitmask. If you've got the OA in a day or two, this is the pattern to lock in. StealthCoder sits behind it as a safety net if your mind goes blank on the live assessment.
The problem
You are given an array items of distinct clothing-item labels and an array illegalOutfits. Each row [a, b] in illegalOutfits identifies two different labels that may not appear together. An outfit is a non-empty subset of items. An outfit is legal when it does not contain both labels from any forbidden pair. Repeated forbidden rows describe the same restriction. Return the number of legal outfits as a signed 64-bit integer. Function countLegalOutfits(items: String[], illegalOutfits: String[][]) → long Examples Example 1 items = ["A","B","C"] illegalOutfits = [["A","B"],["A","C"]] return = 4 The legal non-empty subsets are [A], [B], [C], and [B, C]. Every other non-empty subset contains A together with B or C. Example 2 items = ["hat","shirt","pants","shoes"] illegalOutfits = [["hat","shirt"],["pants","shoes"]] return = 8 For each forbidden pair, choose neither label or exactly one of its two labels. The two independent pairs therefore produce 3 * 3 = 9 subsets including the empty subset, so there are 8 legal outfits. Constraints 1 <= items.length <= 20. Every value in items is a distinct non-empty string. 0 <= illegalOutfits.length <= 100. Every row in illegalOutfits contains exactly two distinct labels from items. Repeated forbidden rows are allowed and represent the same restriction. The answer fits in a signed 64-bit integer.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Map each label to an index 0-19. For every forbidden row, set a bit in an adjacency mask: adj[a] |= 1<<b, and the same for b. Dedupe is automatic because OR is idempotent, which handles repeated rows. Then loop mask from 1 to (1<<n)-1. A subset is legal if, for every set bit i, adj[i] & mask is zero. That's about 2^20 times 20 operations, which is fine. The common pitfalls are counting the empty subset, forgetting to dedupe the label-to-index map, and using a 32-bit int for the result. A faster option is a recursive include-or-skip search that prunes when a conflict appears. If you freeze during the live OA, StealthCoder can hand you the bitmask skeleton so you only have to verify the edge cases.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Count Legal Outfit Combinations cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Duolingo's OA.
Duolingo reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Count Legal Outfit Combinations FAQ
What's the trick in Count Legal Outfit Combinations?+
Treat it as counting independent sets. Items are nodes, illegal pairs are edges, and you count non-empty subsets with no edge inside. Since n is at most 20, brute-force every subset with a bitmask and check each against adjacency masks.
How hard is this problem really?+
Easy to medium. The idea is simple once you see the graph, and the n <= 20 limit tells you exponential enumeration is intended. Most mistakes come from the empty subset, string-to-index mapping, and duplicate rows, not from the algorithm.
Do I need dynamic programming or is brute force enough?+
Brute force is enough. 2^20 is about a million masks, and checking each in 20 steps is fast. A backtracking search that skips conflicting items works equally well and can prune early. No DP table is required for these constraints.
How do I handle the repeated forbidden rows?+
Store restrictions as bits in an adjacency mask per item. Setting the same bit twice changes nothing, so duplicates vanish without extra code. Just map each label to its index through a hash map first, then OR the bits in for both directions.
How should I prepare for this in 48 hours?+
Write the bitmask version from scratch once, then the include-or-skip backtracking version. Test with the two examples, expecting 4 and 8. Make sure you return a long and subtract the empty set. That covers nearly every way this question can go wrong.