Generate Parentheses

Problem Statement

The task is to create a function that generates all possible well-formed combinations of parentheses for a given number of pairs. A combination is considered well-formed if every opening parenthesis "(" has a corresponding closing parenthesis ")" and the pairs are correctly nested. For instance, with three pairs (n = 3), some valid combinations include "((()))", "(()())", and "()(())", among others. The goal is to generate all such possible combinations for any given n within the constraints.

Examples

Example 1

Input:

n = 3

Output:

["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input:

n = 1

Output:

["()"]

Constraints

• 1 <= n <= 8

Approach and Intuition

The challenge of generating well-formed parentheses can be approached recursively or using iterative methods such as backtracking, which is well-suited for this kind of problem where we need to explore all possible combinations under certain constraints. Here’s the intuitive breakdown of this process:

1. Initialization:

   • Start with an empty string and initiate the process with the total number of opening and closing brackets set to n.

2. Recursive Backtracking Function:

   • The recursive function takes the current string in construction, the remaining count of opening brackets, and closing brackets.

   • Base Case:

     • When both the remaining opening and closing brackets count reaches zero, a valid combination has been formed. This combination is added to the result list.

   • Recursive Case:

     • If the count of remaining opening brackets > 0, a new combination can be formed by adding an opening bracket and recursively calling the function with decremented count of opening brackets.

     • If the count of remaining closing brackets is greater than the count of remaining opening brackets, a closing bracket can be added. This ensures that no closing bracket is added without a corresponding opening bracket before it, maintaining the well-formed criterion.

3. Backtracking:

   • This is inherent in the recursive approach as it explores one branch (like adding an opening bracket), reaches an end (either finding a valid combination or violating the well-formed rule), and then returns to explore the other branch (adding a closing bracket).

This approach effectively builds all combinations by adding parentheses step-by-step, while the recursive structure ensures that only valid sequences are created and added to the list. The constraints of n being between 1 and 8 inclusively guarantee that the recursion depth and computational cost remain feasible.

Solutions

class Solution {
public:
    std::vector<std::string> createParentheses(int count) {
        if (count == 0) {
            return std::vector<std::string>{""};
        }
        std::vector<std::string> result;
        for (int lc = 0; lc < count; ++lc) {
            for (std::string lPart : createParentheses(lc)) {
                for (std::string rPart : createParentheses(count - 1 - lc)) {
                    result.push_back("(" + lPart + ")" + rPart);
                }
            }
        }
        return result;
    }
};