# Generate Parentheses
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/generate-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/generate-parentheses
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Avito](https://scaleengineer.com/companies/avito), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Huawei](https://scaleengineer.com/companies/huawei), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Airtel](https://scaleengineer.com/companies/airtel), [Lucid Motors](https://scaleengineer.com/companies/lucid-motors), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Netflix](https://scaleengineer.com/companies/netflix), [Veeva Systems](https://scaleengineer.com/companies/veeva-systems), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Zenefits](https://scaleengineer.com/companies/zenefits), [BlackRock](https://scaleengineer.com/companies/blackrock), [Disney](https://scaleengineer.com/companies/disney), [PhonePe](https://scaleengineer.com/companies/phonepe), [Texas Instruments](https://scaleengineer.com/companies/texas-instruments), [Amdocs](https://scaleengineer.com/companies/amdocs), [Grammarly](https://scaleengineer.com/companies/grammarly), [Point72](https://scaleengineer.com/companies/point72)
---
## Problem
Given `n` pairs of parentheses, write a function to _generate all combinations of well-formed parentheses_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `1 <= n <= 8`

# Approaches
## Brute Force
This approach involves generating every possible sequence of length `2n` using `n` opening and `n` closing parentheses. After generating a sequence, it is checked for well-formedness. If it's valid, it's added to the list of results.
**Time:** O(n * 2^(2n)) · **Space:** O(n)
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Generates a massive number of invalid combinations that are later discarded.; Will likely result in a 'Time Limit Exceeded' error for `n` greater than a small value.
### Explanation
The brute-force method is the most straightforward way to approach the problem. We generate all possible strings of length `2n` that can be formed using the characters `(` and `)`. This results in `2^(2n)` possible strings. For each generated string, we then perform a check to see if it's a valid, well-formed parenthesis string. A string is considered valid if it contains an equal number of opening and closing parentheses and if, at any point from left to right, the count of closing parentheses never exceeds the count of opening parentheses. While simple to understand, this method is highly inefficient because it explores a vast number of invalid combinations.

```java
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    private void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (isValid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    private boolean isValid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return (balance == 0);
    }
}
```
### Algorithm
- Create a recursive function, say `generateAll(char[] current, int pos, List<String> result)`.
- The function will try to place either a `(` or a `)` at each position `pos` of a character array `current` of size `2*n`.
- The recursion proceeds from `pos = 0` to `2*n - 1`.
- **Base Case:** When `pos` reaches `2*n`, the character array is full. At this point, a validation function `isValid(current)` is called.
- The `isValid` function checks two conditions:
  1. The total count of `(` equals the total count of `)`.
  2. At no point during a left-to-right scan does the count of `)` exceed the count of `(`.
- If `isValid` returns true, the string representation of the `current` array is added to the final result list.

## Dynamic Programming
This approach uses dynamic programming to build the solution for `n` pairs by leveraging the solutions for smaller numbers of pairs. It's based on the idea that any well-formed parenthesis string can be decomposed into smaller well-formed strings.
**Time:** O(4^n / sqrt(n)) · **Space:** O(4^n / sqrt(n))
**Pros:** Systematic and guaranteed to find all solutions without repetition.; Avoids recomputing solutions for the same subproblem.
**Cons:** Requires significant space to store the results of all subproblems from `0` to `n-1`.
### Explanation
The dynamic programming approach, also known as the closure number method, constructs the solution iteratively. We define `dp[i]` as the list of all valid combinations for `i` pairs of parentheses. We build up the `dp` table from `i=0` to `n`.

Any non-empty well-formed parenthesis string `S` can be uniquely decomposed into the form `S = "(" + A + ")" + B`, where `A` and `B` are themselves well-formed parenthesis strings (which can be empty). If `S` has `i` pairs, and we let `A` have `j` pairs, then `B` must have `i - 1 - j` pairs. By iterating through all possible values of `j` (from `0` to `i-1`), we can generate all combinations for `i` pairs by combining the pre-computed results from `dp[j]` and `dp[i-1-j]`.

```java
class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }
        
        dp.get(0).add("");
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                List<String> list1 = dp.get(j);
                List<String> list2 = dp.get(i - 1 - j);
                for (String s1 : list1) {
                    for (String s2 : list2) {
                        dp.get(i).add("(" + s1 + ")" + s2);
                    }
                }
            }
        }
        return dp.get(n);
    }
}
```
### Algorithm
- Let `dp[i]` be the list of all well-formed parenthesis combinations of `i` pairs.
- The base case is `dp[0]`, which contains a single empty string: `[""]`.
- To compute `dp[i]` for `i > 0`, we iterate through all possible splits. Any well-formed string `S` can be written as `S = "(" + A + ")" + B`, where `A` and `B` are also well-formed strings.
- If `A` has `j` pairs of parentheses, then `B` must have `i - 1 - j` pairs.
- We loop `j` from `0` to `i-1`.
- For each `j`, we combine every string from `dp[j]` (for `A`) with every string from `dp[i-1-j]` (for `B`).
- The new string `"(" + A + ")" + B` is added to `dp[i]`.
- The final answer is `dp[n]`.

## Backtracking
This is the most efficient approach, which builds the parenthesis strings recursively. It adds either an opening or a closing parenthesis at each step, but only if it maintains the properties of a well-formed string. This pruning of the search space makes it very fast.
**Time:** O(4^n / sqrt(n)) · **Space:** O(n)
**Pros:** Highly efficient with optimal time complexity.; Minimal space complexity, using only O(n) space for the recursion stack.; Effectively prunes the search tree, exploring only valid combinations.
**Cons:** Recursion can be slightly less intuitive than an iterative DP approach for some developers.
### Explanation
The backtracking approach constructs the solution incrementally, ensuring that every partial solution (prefix) is valid. We use a recursive function that maintains the current string being built, and the counts of open and close parentheses used so far.

The recursion is guided by two simple constraints:
1. We can add an opening parenthesis `(` only if we have used fewer than `n` open parentheses.
2. We can add a closing parenthesis `)` only if the number of closing parentheses is strictly less than the number of open parentheses. This is the key constraint that ensures well-formedness, as it prevents prefixes like `())`.

The recursion terminates when the length of the string reaches `2n`, at which point we have a complete, valid combination. By only exploring valid paths, this method avoids the unnecessary work of the brute-force approach and has a much better space complexity than the DP approach.

```java
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current.toString());
            return;
        }

        if (open < max) {
            current.append("(");
            backtrack(result, current, open + 1, close, max);
            current.deleteCharAt(current.length() - 1); // backtrack
        }

        if (close < open) {
            current.append(")");
            backtrack(result, current, open, close + 1, max);
            current.deleteCharAt(current.length() - 1); // backtrack
        }
    }
}
```
### Algorithm
- Define a recursive function, e.g., `backtrack(result, current_string, open_count, close_count, n)`.
- **Base Case:** If the length of `current_string` is `2 * n`, a valid combination is found. Add it to the `result` list and return.
- **Recursive Step 1 (Add ')'):** If the number of open parentheses used (`open_count`) is less than `n`, we can add an opening parenthesis. Append `(` to `current_string` and make a recursive call with `open_count + 1`.
- **Recursive Step 2 (Add ')'):** If the number of close parentheses used (`close_count`) is less than the number of open parentheses used (`open_count`), we can add a closing parenthesis. Append `)` to `current_string` and make a recursive call with `close_count + 1`.
- After each recursive call, backtrack by removing the last character added to `current_string` to explore other possibilities.
- The initial call is `backtrack([], "", 0, 0, n)`.

# Solutions
### CSharp

```csharp
public class Solution {
    private List < string > ans = new List < string > ();
    private int n;
    public List < string > GenerateParenthesis(int n) {
        this.n = n;
        Dfs(0, 0, "");
        return ans;
    }
    private void Dfs(int l, int r, string t) {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.Add(t);
            return;
        }
        Dfs(l + 1, r, t + "(");
        Dfs(l, r + 1, t + ")");
    }
}
```

### Java

```java
class Solution {
private
  List<String> ans = new ArrayList<>();
private
  int n;
public
  List<String> generateParenthesis(int n) {
    this.n = n;
    dfs(0, 0, "");
    return ans;
  }
private
  void dfs(int l, int r, String t) {
    if (l > n || r > n || l < r) {
      return;
    }
    if (l == n && r == n) {
      ans.add(t);
      return;
    }
    dfs(l + 1, r, t + "(");
    dfs(l, r + 1, t + ")");
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {string[]} */ var generateParenthesis =
  function (n) {
    function dfs(l, r, t) {
      if (l > n || r > n || l < r) {
        return;
      }
      if (l == n && r == n) {
        ans.push(t);
        return;
      }
      dfs(l + 1, r, t + " ( ");
      dfs(l, r + 1, t + " ) ");
    }
    let ans = [];
    dfs(0, 0, "");
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<string> generateParenthesis(int n) {
    vector<string> ans;
    function<void(int, int, string)> dfs = [&](int l, int r, string t) {
      if (l > n || r > n || l < r)
        return;
      if (l == n && r == n) {
        ans.push_back(t);
        return;
      }
      dfs(l + 1, r, t + "(");
      dfs(l, r + 1, t + ")");
    };
    dfs(0, 0, "");
    return ans;
  }
};

```

### Python

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]: def dfs(l, r, t): if l > n or r > n or l < r: return if l == n and r == n: ans . append(t) return dfs(l + 1, r, t + '(') dfs(l, r + 1, t + ')') ans = [] dfs(0, 0, '') return ans  # class Solution ( object ): def generateParenthesis ( self , n ): """ :type n: int :rtype: List[str] """ def dfs ( left , path , res , n ): if len ( path ) == 2 * n : if left == 0 : res . append ( "" . join ( path )) return if left < n : path . append ( "(" ) dfs ( left + 1 , path , res , n ) path . pop () if left > 0 : path . append ( ")" ) dfs ( left - 1 , path , res , n ) path . pop () res = [] dfs ( 0 , [], res , n ) return res

```