Solution: Generate Parentheses

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #22 (Medium): Generate Parentheses

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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);
    }
};