来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

1. 题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

• 示例：
  输入：n = 3
  输出：[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
  ]

class Solution {
 public List<String> generateParenthesis(int n) {
      
    }
}

2.JAVA解答

先写一个判断是否括号都满足的函数，然后DFS深度递归遍历，达到最深层，判断括号是否满足，满足则加入结果集，不满足则跳过该答案。

class Solution {
    public boolean isValid(String s){
        if(s.length()%2==1){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push('(');
            }else{
                if(stack.size()==0){
                    return false;
                }
                stack.pop();
            }
        }
        return true;
    }

    public void generatParenthesis2(List<String> res,String nStr,
                                    int leftNum,int rightNum){
        if(leftNum<0 || rightNum<0){
            return;
        }                                
        if(leftNum>0 && rightNum==0){
            return;
        }
        if(leftNum==0 && rightNum==0){
            if(isValid(nStr)){
                res.add(nStr);    
            }
            return;
        }
        generatParenthesis2(res,nStr+"(",leftNum-1,rightNum);
        generatParenthesis2(res,nStr+")",leftNum,rightNum-1);
    }
    
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        generatParenthesis2(res,"",n,n);
        return res;
    }
}