How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Disney.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Disney during technical interviews.

Generate All Valid Combinations of Balanced Parentheses

Quick Overview

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.

Company: Disney

Role: Data Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## 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.

Quick Answer: 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.

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 (this console compares against the lexicographically sorted list, so return your results sorted to match). **Example 1:** `n = 3` → `["((()))", "(()())", "(())()", "()(())", "()()()"]` **Example 2:** `n = 1` → `["()"]` **Example 3:** `n = 0` → `[""]`

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.
For n = 0 the output is a list containing the single empty string: [""].

Examples

Input: (3,)

Expected Output: ['((()))', '(()())', '(())()', '()(())', '()()()']

Explanation: n = 3: there are Catalan(3) = 5 well-formed strings, shown in lexicographic order.

Input: (1,)

Expected Output: ['()']

Explanation: n = 1: the only balanced string is '()'.

Input: (0,)

Expected Output: ['']

Explanation: Boundary: n = 0 yields exactly one string, the empty string.

Input: (2,)

Expected Output: ['(())', '()()']

Explanation: n = 2: Catalan(2) = 2 valid strings.

Input: (4,)

Expected Output: ['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']

Explanation: n = 4: Catalan(4) = 14 valid strings, sorted lexicographically.

Hints

Build strings character by character with backtracking. Track how many '(' and ')' you have placed so far.
You may add a '(' as long as you have used fewer than n opening brackets. You may add a ')' only when the count of ')' placed is strictly less than the count of '(' placed — this keeps every prefix valid.
Stop and record the string once its length reaches 2n. Return the collected strings sorted so the output ordering is deterministic.

Quick Overview