Generate Parentheses

• medium
• tag: bakctracking
• similar: 8 queens

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()"

思路

• 使用回溯法.
• 这里主要是分2种情况recursion call: 若left没用完, 可以接着用open. 若此时left > right, 可以使用close.
• 但是我错在这个Backtracking上了, 即回溯之后, 并没有全部回溯到之前的state!

idea 1: 错误的回溯

• 截图如下:

• 如图所示: 在第一个if的情况下, return, 然后到箭头所指的地方, 此时path是((, 但是left却是1. 这是为何?

  • 我的想法是此时应该是(, 因为已经回溯到第一层了. 但为什么path有回溯? 从而导致了继续向下, 得到(()(!
  • 原因是: 第一个if的情况下的return之后, 直接进入第二个if, 而这中间并没有Backtracking!
  • 解决方法很简单, 就是2个if都要Backtracking.

• 所以回溯到之前的状态是关键.

• 错误代码如下:

private void backWRONG(int n, int left, int right, List<String> result, StringBuilder path) {
    if (path.length() == n*2) {
      String tmp = path.toString();
      result.add(tmp);
      return;
    }
    if (left < n)
      backWRONG(n, left + 1, right, result, path.append('('));
    if (left > right)
      backWRONG(n, left, right + 1, result, path.append(')'));
    path.deleteCharAt(path.length() - 1);
  }

idea 2: 正确的回溯

• 代码如下:

`java private void back(int n, int left, int right, List<String> result, StringBuilder path) { if (path.length() == n*2) { //String tmp = path.toString(); result.add(path.toString()); return; } if (left < n) { back(n, left + 1, right, result, path.append('(')); path.deleteCharAt(path.length() - 1); } if (left > right) { back(n, left, right + 1, result, path.append(')')); path.deleteCharAt(path.length() - 1); } }