← Create New Paste

Generate Parentheses in a Coding Interview: Backtracking With Open and Close Counts

4 views
"Generate Parentheses" asks for every valid combination of n pairs of parentheses. For n = 3 the answer has five strings: "((()))", "(()())", "(())()", "()(())", and "()()()". It is a compact problem, which is exactly why interviewers like it: in fifteen minutes they can see whether you understand pruning, recursion state, and how to reason about output size. Start with the brute force, then reject it You could generate all 2^(2n) strings of length 2n and keep the valid ones. Mention this in one sentence to show you see the baseline, then explain why it wastes work: most strings are invalid, and you can tell they are invalid long before they are complete. The two rules that make it efficient Build the string one character at a time and track two counts: open (how many "(" you have placed) and close (how many ")" you have placed). 1. You may add "(" if open < n. 2. You may add ")" only if close < open. The second rule is the key insight. It guarantees that every prefix you build has at least as many opening as closing brackets, so you never construct a string that is already broken. When the string reaches length 2n, it is valid by construction, so you add it to the result without any extra check. The code shape A recursive helper takes the current string (or a character buffer), open, and close. If the length is 2n, record the result and return. Otherwise, try "(" if allowed, then ")" if allowed. With a mutable buffer, append before the recursive call and remove after it; this is the classic choose, explore, un-choose pattern. With immutable strings, passing current + "(" is simpler and still fine for interview-sized n. Complexity, explained honestly The number of valid outputs is the nth Catalan number, which grows roughly like 4^n / (n^1.5). Each output has length 2n, so total time is about O(4^n / sqrt(n)). Many candidates just say "exponential"; giving the Catalan bound, even approximately, is a nice signal. Space is O(n) for the recursion depth, plus the output. Follow-ups to be ready for - "Can you do it iteratively?" Use an explicit stack of (string, open, close) tuples. - "Check if a given string is valid" - a single counter that must never go negative and must end at zero. - "What about multiple bracket types?" Validity then needs a stack, and generation needs to track which type to close next. - Dynamic programming: every valid string can be written as "(" + A + ")" + B, where A and B are smaller valid strings. This builds answers for n from answers for smaller sizes. How to present it Draw the decision tree for n = 2 and show where branches get pruned. Then code, then trace one path. Talking through the invariant ("close never exceeds open") is what makes the solution convincing. Practicing this out loud is the best preparation. For support in the real session, Linkjob AI (https://linkjob.ai) offers real-time help during live job interviews and technical interviews, which can help you keep your explanation structured while you code.
Created Nov 17, 2026 14:32 Expires Nov 17, 2027 14:32