# 22 Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given `n= 3`, a solution set is:

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

**The Idea:** Recursive build from the base case where if n = 0, then sol = { "" }, and if n = 1, then sol = { "()" }. If we continue this pattern, we will notice that every nth case can be built from n-1th case. That is, for every nth case, we insert a parenthesis pair "()" to every left parenthesis. Additionally, we insert a parenthesis pair at the beginning. To take care of duplicates, use an unordered\_set. One big problem with this implementation is that we end up calculating a lot of redundent parenthesis sets.

**Complexity:** ![](/files/-LoJImo_TX9kd-2KwIvF)

```cpp
vector<int> find_left_paren_loc(const string &s) {
    vector<int> locs;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            locs.push_back(i);
    }
    return locs;
}

vector<string> _generateParenthesis(int n, vector<string> &prev, unordered_set<string> &unique) {
    if (n > 0) {
        vector<string> next;
        for (string &s : prev) {

            vector<string> candidates;
            vector<int> left_locs = find_left_paren_loc(s);
            for (int i : left_locs) {
                string str_cp = s;
                candidates.push_back(str_cp.insert(i + 1, "()"));
            }
            candidates.push_back("()" + s);

            for (const string &s1 : candidates) {
                if (unique.find(s1) == unique.end()) {
                    next.push_back(s1);
                    unique.insert(s1);
                }
            }
        }
        return _generateParenthesis(n - 1, next, unique);
    }

    return prev;
}

vector<string> generateParenthesis(int n) {
    unordered_set<string> unique;
    vector<string> prev;

    prev.push_back("");
    return _generateParenthesis(n, prev, unique);
}


int main() 
{
    for (int i : {0, 1, 2, 3, 4, 5, 6}) {
        print(generateParenthesis(i));
        cout << endl;
    }
}
```

**Solution 2 with optimal time complexity:**

Maintain two integers which will denote the number of remaining left and right parenthesis. Initially, we know that we need `n` left parenthesis and as a general rule, we can only have a right parenthesis if the current number of left parenthesis exceeds the number of right parenthesis. For example, if we have 0 left parenthesis, then there is no way we can have a right. However, when we have 2 left parenthesis - we can branch out with a right. So it follows that number of left parenthesis can only decrease, while the number or right parenthesis can only increase only when a left parenthesis is introduced.![](/files/-LoJImob3Hv-VuZzUNxr)

```python
class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        solutions = []
        def __generateParenthesis(cur, left, right):
            if left == 0 and right == 0:
                solutions.append(cur)
            else:
                if right:
                    __generateParenthesis(cur + ')', left, right - 1)
                if left:
                    __generateParenthesis(cur + '(', left - 1, right + 1)

        __generateParenthesis('', n, 0)
        return solutions


obj = Solution()
print(obj.generateParenthesis(4))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/22-generate-parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.