Medium · Constrained Backtracking
Understand → Visualise → Practice.
Generating every 2n-character string wastes time on impossible prefixes. Track how many opening and closing brackets have been used.
Add `(` while opened < n; add `)` only while closed < opened.
Use an opening bracket if any remain.
A closing bracket needs an unmatched opener.
Length 2n with equal counts is complete.
O(Cₙ·n) output time for the nth Catalan number Cₙ, with O(n) recursion depth.
Checking validity only at the leaves explores exponentially many prefixes that can never recover.
Read the full guide first: Recursion and Backtracking.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.