Katkat
Back

Generate All Valid Combinations of Balanced Parentheses

DisneyData Engineer · Online Assessment
MediumData EngineerOnline AssessmentCoding & Algorithms

Last updated

This question tests a candidate's ability to apply recursive backtracking and combinatorial generation in a coding interview context. It evaluates understanding of constraint-based enumeration and string construction, core algorithmic skills frequently assessed in software engineering and data engineering roles.

Generate All Valid Combinations of Balanced Parentheses

Given an integer n representing the number of pairs of parentheses, generate all distinct strings of well-formed (balanced) parentheses using exactly n pairs.

A string is well-formed if every opening parenthesis ( has a matching closing parenthesis ) and the parentheses are properly nested — equivalently, scanning left to right the number of ) never exceeds the number of (, and the totals are equal at the end.

Return the list of all such strings. The order of the strings in the output does not matter.

Examples

Example 1

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

Example 2

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

Example 3

Input: n = 0
Output: [""]

Constraints

  • 0 <= n <= 8
  • Every string in the output uses exactly n opening and n closing parentheses.
  • All strings in the output must be distinct and well-formed.