Katkat
Back

Generate All Well-Formed Parenthesis Strings

DisneyData Engineer · Online Assessment
MediumData EngineerOnline AssessmentCoding & Algorithms

Last updated

This question tests practical understanding of recursion and backtracking through enumeration of all valid parenthesis combinations of a given length. It is a classic coding interview problem that evaluates combinatorial reasoning, constraint-based pruning, and familiarity with Catalan number sequences in algorithm design.

A string of parentheses is called well-formed if every opening bracket ( has a matching closing bracket ) and the brackets are correctly nested. For example, (()) and ()() are well-formed, while )(, ((), and ())( are not.

Given an integer n, generate all well-formed strings that use exactly n opening brackets and n closing brackets (so each string has length 2 * n). Return them as a list. The order of the strings in the returned list does not matter, but every returned string must be distinct.

Examples

Example 1

Input: n = 1
Output: ["()"]

Example 2

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

(Any ordering of these 5 strings is accepted.)

Example 3

Input: n = 0
Output: [""]

The only string using zero opening and zero closing brackets is the empty string, which is considered well-formed.

Constraints

  • 0 <= n <= 8
  • Every string in the output must be well-formed, must contain exactly n opening and n closing brackets, and must be unique.
  • The number of valid strings grows as the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ (e.g., $C_8 = 1430$), so the output can be large but is bounded.