PPractick

The problem

A code-formatting tool's test suite needs every well-formed arrangement of n pairs of parentheses, like (())() or ((())), to check that its parser handles all of them. A string is well formed if every ) closes an earlier unmatched ( and all of them are closed at the end. Instead of generating all 2²ⁿ strings and filtering, backtracking tracks two counters: an ( is allowed while fewer than n have been used, and a ) only while it has an unmatched ( to close.

Example: n = 3 → ((())) (()()) (())() ()(()) ()()().

Function signature

vector<string> generateParenthesis(int n);  // shown here in lexicographic order

Test cases

Input n	Output	Explanation
3	((())) (()()) (())() ()(()) ()()()	5 strings
1	()
2	(()) ()()
4	14 strings	The counts are Catalan numbers

(Confirm: 1 ≤ n ≤ 8; any order is acceptable, and this solution produces lexicographic order because '(' sorts before ')'.)

How interviewers phrase it

• "Given n pairs of parentheses, generate all combinations of well-formed parentheses" (LeetCode 22).

Clarifying questions to ask

1. Only one type of bracket? (Yes.)
2. Does the output order matter?
3. How large can n be? (Up to 8: the output grows like the Catalan numbers.)

Follow-ups to expect

1. "What are the two rules?"
2. "Why never check validity at the end?"
3. "How many results are there?"
4. "Complexity?"
5. "How would you check a string is valid?"

Related questions

• Generate Binary Strings Without Consecutive 1s Medium
• Power Set Medium
• Combination Sum Medium
• Combination Sum II Medium
• Subsets I Medium
• Subsets II Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in