Reference: LeetCode EPI 15.7
Difficulty: Medium

My Post: Java B-F & Backtracking Solutions with Detailed Explanations and Comments (easy-understand)

Problem

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

Example: 

1
2
3
4
5
6
7
For example, given n = 3, a solution set is: [
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Analysis

Brute-Force

It is actually a backtracking method without pruning.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public List<String> generateParenthesis(int n) {
  List<String> result = new ArrayList<>();
  StringBuilder sb = new StringBuilder();
  generate(n, 0, sb, result);
  return result;
}

private void generate(int n, int d, StringBuilder sb, List<String> result) {
  if (d >= n * 2) {
    String s = sb.toString();
    if (isValidString(s, n)) { // O(N)
      result.add(s);
    }
    return;
  }
  
  sb.append("(");
  generate(n, d + 1, sb, result);
  sb.setLength(sb.length() - 1);
  
  sb.append(")");
  generate(n, d + 1, sb, result);
  sb.setLength(sb.length() - 1);
}

private boolean isValidString(String str, int n) { // validity
  int L = n, R = n;
  for (char ch : str.toCharArray()) {
    if (ch == '(') L -= 1;
    else           R -= 1;
    // check
    if (L < 0 || R < 0 || L > R) {
      return false;
    }
  }
  return true;
}

Time: $O(N \times 2^{2N})$
Space: $O(N \times 2^{2N})$

Backtracking

Based on the previous brute-force solution, we actually add some code of pruning, which cuts unnecessary recursive calls in backtracking.

The core idea is that we allow L is temporarily greater than R because we can append more ) to satisfy L == R in the future.

However, we don’t allow L < R at any time to occur, e.g. ()) (L = 1, R = 2), ) (L = 0, R = 1). The reason is that it is impossible that these strings would develop to any valid strings in the future. So we should stop trying right away.

Therefore, pruning is based on this idea, so during backtracking we should not allow:

  • L > n or R > n
  • L < R

L and R are the numbers of ( and ).

Then we can append these conditions in the base-case section (check out the first version below).

In an opposite perspective, we allow the following situations to occur:

  • L <= n and R <= n
  • L >= R

In other words, when adding ( we should guarantee that L < n; when adding ) we should guarantee that R < n and L > R.

Then we can append these conditions before doing recursive calls (check out the second version below).

First version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public List<String> generateParenthesis(int n) {
  List<String> result = new ArrayList<>();
  StringBuilder sb = new StringBuilder();
  backtrack(0, 0, n, sb, result);
  return result;
}

// L: # of "("
// R: # of ")"
private void backtrack(int L, int R, int n, StringBuilder sb, List<String> result) {
  // base case
  if (L > n || R > n || L < R) { // the third case: "())"
    return;
  }
  
  if (L == n && R == n) {
    result.add(sb.toString());
    return;
  }
  
  // select "("
  sb.append('(');
  backtrack(L + 1, R, n, sb, result);
  sb.setLength(sb.length() - 1);
  
  // select ")"
  sb.append(')');
  backtrack(L, R + 1, n, sb, result);
  sb.setLength(sb.length() - 1);
}

Second version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void backtrack(int L, int R, int n, StringBuilder sb, List<String> result) {
  // base case
  if (L == n && R == n) { // add to the result
    result.add(sb.toString());
    return;
  }
  
  // we allow L > R (temporarily), but don't allow L < R at any time.
  
  // select "("
  if (L < n) { // consider when we can add "("
    sb.append('(');
    backtrack(L + 1, R, n, sb, result);
    sb.setLength(sb.length() - 1);
  }
  
  // select ")"
  if (R < n && L > R) { // consider when we can add ")"
    sb.append(')');
    backtrack(L, R + 1, n, sb, result);
    sb.setLength(sb.length() - 1);
  }
}

Time: $O(\frac{4^N}{\sqrt{n}})$
Space: $O(\frac{4^N}{\sqrt{n}})$