22. Generate Parentheses

Generate Parentheses

Problem Description

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

Approach) Dynamic Programming

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 closing 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.

Code:

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

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

Approach) Breadth-First Search and Recursion

The below code sample starts with a variable to store the results. 

The second line calls a breadth-first search algorithm that will build a string of appropriate parentheses pairs. 

The third line returns the result. The following lines are a closure or inner function that is used only within the general parentheses function.

The breadth-first search function has access to the number given in the general parentheses function and acts as a recursive function with the base case pushing a combination parentheses string into the “result” variable. The first combination that the recursive function will store if the number inputted is 3 — [“((()))”]. 

From there, the breadth-first search function will start a parentheses combination with fewer opening parentheses and ultimately form all possible combinations.

Code:

const generateParentheses = (n) => {
  const result = [];
  breathFirstSearch("", 0, 0);
  return result;
  function breathFirstSearch(str, left, right) {
    if (left === n && right === n) {
      result.push(str);
      return;
    }
    if (left !== n) {
      breathFirstSearch(str + "(", left + 1, right);
    }
    if (left > right) {
      breathFirstSearch(str + ")", left, right + 1);
    }
  }
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #22. Generate Parentheses

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!