括号生成

描述：
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思想：dfs+剪枝

class Solution {
  public List<String> generateParenthesis(int n) {
    String str = "()";
    List<String> res = new ArrayList<>();
    if(n==0) {
      return res;
    }
    LinkedList<Character> temp = new LinkedList<>();
    int left = 0;
    int right = 0;
    dfs(str,res,temp,n,left,right);
    return res;
  }

  private void dfs(String str, List<String> res, LinkedList<Character> temp, int n, int left, int right) {
    if(temp.size()==2*n) {
      if(isFit(temp)) {
        add2Temp(res,temp);
      }
      return;
    }
    if(left>n || right>n) {
      return;
    }

    for(int i=0;i<str.length();i++) {
      temp.add(str.charAt(i));
      if(i==0) {
        dfs(str,res,temp,n,left+1,right);
      }else {
        dfs(str,res,temp,n,left,right+1);
      }
      temp.pollLast();
    }
  }

  private boolean isFit(LinkedList<Character> temp) {
    LinkedList<Character> stack = new LinkedList<>();
    for(int i=0;i<temp.size();i++) {
      char c = temp.get(i);
      if(stack.size()==0) {
        stack.add(c);
      }else {
        if(c==')' && stack.getLast()=='(') {
          stack.pollLast();
        }else {
          stack.add(c);
        }
      }
    }
    return stack.size()==0;
  }

  private void add2Temp(List<String> res, LinkedList<Character> temp) {
    StringBuffer s = new StringBuffer();
    for(int i=0;i<temp.size();i++) {
      s.append(temp.get(i));
    }
    res.add(s.toString());
  }
}