public class Solution {    public List
      
        generateParenthesis(int n) {        List
       
         results = new ArrayList<>();        if (n == 0) {            return results;        }        generate(0, 2 * n, "", results);        return results;    }    private void generate(int level, int n, String curState, List
        
          results) {        //recursion terminstor 先写        if (level >= n) {            //方法一：此处判断是否合法            if (isValid(curState)) {                results.add(curState);            }                        return;        }        generate(level + 1, n, curState + "(", results);               generate(level + 1, n, curState + ")", results);    }    private boolean isValid(String s) {        char[] c = s.toCharArray();        Stack stack = new Stack();        for (int i = 0; i < c.length; i++) {            if(c[i] == ')' && !stack.isEmpty()) {                stack.pop();            } else if (c[i] == '(') {                stack.push(c[i]);            } else {                return false;            }        }        if (stack.isEmpty()) {            return true;        }        return false;    }}
        
       
      

O(T)有问题

应该每步进行判断。

public class Solution {    public List
      
        generateParenthesis(int n) {        List
       
         results = new ArrayList<>();        if (n == 0) {            return results;        }        gen(n, n, "", results);        return results;    }    private void gen(int left, int right, String cur, List
        
          results) {        if (left == 0 && right == 0) {            results.add(cur);        }        if (left > right) {            return;        }        if (left > 0) {            gen(left - 1, right, cur + '(', results);        }        if (right > 0 ) {            gen(left, right - 1, cur + ')', results);        }    }}
        
       
      

思路：先有左括号，再有右括号。