Practice/Microsoft/Leetcode 22. Generate Parentheses

Leetcode 22. Generate Parentheses

CodingOptional

Problem

Given an integer n representing the number of pairs of parentheses, generate all possible combinations of well-formed (balanced and correctly nested) parentheses strings.

A string of parentheses is considered well-formed if:

• Every opening parenthesis ( has a corresponding closing parenthesis )
• At no point while reading left-to-right does the count of closing parentheses exceed the count of opening parentheses

Return all valid combinations in any order.

Requirements

1. Generate all distinct valid parentheses combinations
2. Each combination must use exactly n opening and n closing parentheses
3. All combinations must be properly balanced and nested
4. Return the results as a list of strings

Constraints

• 0 ≤ n ≤ 8
• The number of valid combinations grows according to the Catalan number sequence
• Expected time complexity: O(4^n / √n) - the nth Catalan number bounds
• Expected space complexity: O(n) for recursion depth (excluding output storage)

Examples

Example 1:

Input: n = 1 Output: ["()"] Explanation: Only one way to arrange a single pair of parentheses.

Example 2:

Input: n = 2 Output: ["(())", "()()"] Explanation: Two valid arrangements - nested or sequential.

Example 3:

Input: n = 3 Output: ["((()))", "(()())", "(())()", "()(())", "()()()"] Explanation: Five valid arrangements following all balancing rules.

Example 4:

Input: n = 0 Output: [""] Explanation: The empty string is the only valid sequence with zero pairs.