题解 | JAVA #括号生成# [P0]

对于括号的题，核心基本都是:
  "一个字符串是合法的括号组合"的*充分必要*条件是:
  1. 字符串中开口数等于闭口数 (这是废话)
  2. 字符串的所有prefix都满足: 开口数>=闭口数
    举个栗子，比如 "()(())":
    prefix: "(", "()", "()(", "()((", "()(()", "()(())".

那么对与这道题，为满足1,2, 每一个位置可以有的permutation就是:
1. 如果有多余的开口 -> 可以选开口
2. 如果有多余未闭合的开口 -> 可以选闭口

剩下的就是正常的递归+回溯了
时间: O(2^n), 每一位最多2个permutation
空间: O(n), 栈高是n

import java.util.*;

public class Solution {
    ArrayList<String> ans = new ArrayList<>();
    
    public ArrayList<String> generateParenthesis (int n) {
      permute(n, n, 0, new StringBuilder());
      return ans;
    }
  
    void permute(int open, int close, int unclosedOpen, StringBuilder sb) {
      // base case，开口闭口都用完了
      if (open == 0 && close == 0) {
        ans.add(sb.toString());
        return;
      }
      
      // always ok to pick an open bracket if there are any open-bracket
      if (open > 0) {
        sb.append("(");
        permute(open-1, close, unclosedOpen+1, sb);
        sb.deleteCharAt(sb.length()-1);
      }
      // can pick close bracket if there is any unclosed open-bracket
      if (unclosedOpen > 0) {
        sb.append(")");
        permute(open, close-1, unclosedOpen-1, sb);
        sb.deleteCharAt(sb.length()-1);
      }
    }
}