思路

大问题化成子问题，每次增加分解成两种可能：
1.加“（”，前提“（”数量小于n
2.加“）”，前提“）”数量小于“）”

代码

class Solution {
    public List<String> generateParenthesis(int n) {
      
        List<String> res = new ArrayList<>();
        backtrack(n,res,0,0,"");
        return res;
    }
    public void backtrack(int n, List<String> res,int open,int close,String s){
        if(s.length() == 2*n){
            res.add(s);
        }
        else{
            if(open<n){
               backtrack(n,res,open+1,close,s+"("); 
            }
            if(close<open){
               backtrack(n,res,open,close+1,s+")"); 
            }           
        }
    }
}