Problem Description

Given n number of pairs of parentheses, we need to generate all combinations of well-formed parentheses.

For instance, if n equals 3, the set of well-formed parentheses are as follow:

1
2
3[
4  "((()))",
5  "(()())",
6  "(())()",
7  "()(())",
8  "()()()"
9]

Approach

The solution implements the concept of Depth-First Search (DFS). In this problem, we recursively perform DFS by adding an open parenthesis('(') or a close parenthesis(')') to the current string based on certain conditions until we can form a well-formed parenthesis.

The conditions are:

1. We can add an open parenthesis if the total number of available open parenthesis is less than n.
2. We can add a close parenthesis if the total number of available close parenthesis is less than the total number of open parentheses.

After both open and close parentheses are used up, a well-formed parenthesis has been formed and it is added into the result list.

Example Walkthrough

Take n = 3 as an example. We start by adding an open parenthesis, and then we have two options:

1
2
3(
4((
5(((
6((()
7((())

or

1
2
3(
4((
5(())
6(())
7()()

We continue this process until the total number of open and close parentheses reach n.

Python Solution

1
2python
3class Solution:
4  def generateParenthesis(self, n):
5    def generate(p, left, right, parens=[]):
6      if left:         generate(p + '(', left-1, right)
7      if right > left: generate(p + ')', left, right-1)
8      if not right:    parens += p,
9      return parens
10    return generate('', n, n)

Java Solution

1
2java
3class Solution {
4  private int n;
5  private List<String> output;
6
7  public List<String> generateParenthesis(int n) {
8    this.n = n;
9    this.output = new ArrayList<>();
10    backtrack("", 0, 0);
11    return this.output;
12  }
13
14  private void backtrack(String s, int numOpenParens, int numCloseParens) {
15    if (s.length() == this.n * 2) {
16      this.output.add(s);
17      return;
18    }
19    if (numOpenParens < this.n) {
20      backtrack(s + "(", numOpenParens + 1, numCloseParens);
21    }
22    if (numCloseParens < numOpenParens) {
23      backtrack(s + ")", numOpenParens, numCloseParens + 1);
24    }
25  }
26}

JavaScript Solution

1
2javascript
3class Solution {
4  generateParenthesis(N) {
5    var ans = [];
6    function backtrack(S = '', left = 0, right = 0) {
7      if (S.length === 2 * N) {
8        ans.push(S);
9        return;
10      }
11      if (left < N)    backtrack(S+'(', left+1, right);
12      if (right < left) backtrack(S+')', left, right+1);
13    }
14    backtrack();
15    return ans;
16  }
17}

C++ Solution

1
2c++
3class Solution {
4 public:
5  vector<string> generateParenthesis(int n) {
6    vector<string> ans;
7    dfs(n, n, "", ans);
8    return ans;
9  }
10
11 private:
12  void dfs(int l, int r, string path, vector<string>& ans) {
13    if (l == 0 && r == 0) {
14      ans.push_back(path);
15      return;
16    }
17    if (l > 0) {
18      path.push_back('(');
19      dfs(l - 1, r, path, ans);
20      path.pop_back();
21    }
22    if (l < r) {
23      path.push_back(')');
24      dfs(l, r - 1, path, ans);
25      path.pop_back();
26    }
27  }
28};

C# Solution

1
2csharp
3public class Solution {
4    private IList<string> result;
5    
6    public IList<string> GenerateParenthesis(int n) {
7        result = new List<string>();
8        backtrack("", 0, 0, n);
9        return result;
10    }
11    
12    private void backtrack(string s, int open, int close, int max){
13        if(s.Length == max * 2){
14            result.Add(s);
15            return;
16        }
17        
18        if(open < max)
19            backtrack(s + "(", open + 1, close, max);
20        if(close < open)
21            backtrack(s + ")", open, close + 1, max);
22    }
23}

These solutions use recursion to build up all possible combinations of well-formed parentheses. For every position in the string, we have the option of placing a "(" or a ")". However, we will only place a "(" if we have left ones and only place a ")" if it would not cause a syntax error. This ensures that we do not generate invalid combinations of parentheses.

These DFS-based solutions are time efficient, considering their time complexity are O(4^n / sqrt(n)), which is the nth Catalan number. Considering the requirement of the problem, these solutions are highly optimal and practical.

Time and Space Complexity

The time complexity of generating all well-formed parentheses is O(4^n / sqrt(n)) since each valid sequence has at most n steps during the backtracking procedure.

The space complexity is the same because we need to store all the solutions in the memory.

Possible improvements

While the above solutions are acceptable for small inputs, for larger inputs, other techniques may be required. For example, dynamic programming can be used for catalan number problems like this one, which could potentially speed up the program for large inputs.

Moreover, techniques like memoization could also improve the performance for larger inputs by storing previously computed values. This can help when the function is called repeatedly with the same parameters, saving time by returning the stored values instead of recalculating them. However, the advantage of using memoization would only be seen for larger inputs where the function is often called with the same parameters.