Solution: Generate Parentheses
Tags: algorithms, javascript, java, python
Published: 2021-06-16 08:42:44

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/generate-parentheses/discuss/1276139).*

---

#### [Leetcode Problem #22 (*Medium*): Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given `n` pairs of parentheses, write a function to _generate all combinations of well-formed parentheses_.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| n = 3
Output:| ["((()))","(()())","(())()","()(())","()()()"]
>
Example 2:||
|---:|---|
Input:| n = 1
Output:| ["()"]

---

#### ***Constraints:***
>
 - `1 <= n <= 8`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

We can make short work of this problem with a basic branching **recursive** function (**dfs**). Our recursive function will iterate through the index positions (**pos**) of a possible result. At each **pos**, we can add an open parenthesis if there's more remaining space than unclosed parentheses (**open**) and we can add a closed parenthesis if there are any unclosed parentheses. Once we reach the end of the result, we can add it to our answer array (**ans**).

To make things easier, we can use **bit manipulation** to pass the sequence of parentheses (**seq**) for our potential result as an integer to each new recursion level. Then we just have to translate **seq** to a parentheses string before adding it to **ans**.

Once we're all done, we can just **return ans**.

 - _**Time Complexity: O((2 * N)!/(N! * N!)** reflecting the **2N choose N** possible arrangements of parentheses_
 - _**Space Complexity: O(N)** for the recursion stack and **res**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var generateParenthesis = function(N) {
    let ans = [], m = 2 * N
    
    const dfs = (pos, open, seq) => {
        if (pos === m) {
            let res = new Array(m)
            for (let i = 0; i < m; i++)
                res[i] = seq & 1 << i ? "(" : ")"
            ans.push(res.join(""))
            return
        }
        if (open) dfs(pos+1, open-1, seq)
        if (m - pos > open) dfs(pos+1, open+1, seq | 1 << pos)
    }
    
    dfs(0, 0, 0)
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def generateParenthesis(self, N: int) -> List[str]:
        ans, m = [], 2 * N
        
        def dfs(pos: int, opn: int, seq: int) -> None:
            if pos == m:
                res = [0] * m
                for i in range(m):
                    res[i] = "(" if seq & 1 << i else ")"
                ans.append("".join(res))
                return
            if opn: dfs(pos+1, opn-1, seq)
            if m - pos > opn: dfs(pos+1, opn+1, seq | 1 << pos)
            
        dfs(0, 0, 0)
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public List<String> generateParenthesis(int N) {
        ans = new ArrayList<>();
        m = 2 * N;
        dfs(0, 0, 0);
        return ans;
    }
    
    private List<String> ans;
    private int m;
    
    private void dfs(int pos, int open, int seq) {
        if (pos == m) {
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < m; i++)
                res.append((seq & 1 << i) > 0 ? "(" : ")");
            ans.add(res.toString());
            return;
        }
        if (open > 0) dfs(pos+1, open-1, seq);
        if (m - pos > open) dfs(pos+1, open+1, seq | 1 << pos);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<string> generateParenthesis(int N) {
        m = 2 * N;
        dfs(0, 0, 0);
        return ans;
    }
    
private:
    vector<string> ans;
    int m;
    
    void dfs(int pos, int open, int seq) {
        if (pos == m) {
            string res = "";
            for (int i = 0; i < m; i++)
                res += seq & 1 << i ? "(" : ")";
            ans.push_back(res);
            return;
        }
        if (open) dfs(pos+1, open-1, seq);
        if (m - pos > open) dfs(pos+1, open+1, seq | 1 << pos);
    }
};
```