Given n pairs of parentheses, generate every well-formed combination. Every opening bracket needs a matching closing bracket after it.
DSA Animator › DSA Revision › Backtracking › Generate Parentheses
Remember: open while open is less than n, close while close is less than open. The rules prune every invalid string before it is built. The video solves Generate Parentheses (LeetCode 22, Medium) with the Backtracking with Counts pattern from the Backtracking topic, and you can replay every step in the interactive Generate Parentheses animation.
Given n pairs of parentheses, generate every well-formed combination. Every opening bracket needs a matching closing bracket after it.
For n equal to 3, there are 5 answers. For n equal to 2, there are 2, which are open open close close, and open close open close.
Generating all 2 to the 2n strings and checking each one is wasteful. We can build only valid strings.
Track how many opening and closing brackets are used. You may add an opening bracket while open is less than n. You may add a closing bracket only while close is less than open.
For n equal to 2, start with an empty string and add an opening bracket. Add another opening bracket, and now only closing brackets are allowed, giving open open close close. Backtrack to a single opening bracket, and close it. Now open is less than 2 again, so open and close, giving open close open close. Those are the 2 valid strings, and the same rules give 5 for n equal to 3.
In code, if the length is 2n, record the string. If open is less than n, recurse with an opening bracket added. If close is less than open, recurse with a closing bracket added. The number of answers is the Catalan number, so the work grows with that count.
Remember: open while open is less than n, close while close is less than open. The rules prune every invalid string before it is built.