Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

backtracking

a function to achieve backtracking: 

a list to record all the combination, a string str to record the trial subset at the moment, a number index to record the number of char in the subset, and a number to record left parentheses number(to make sure always on the right way to a valid combination)

1. index=n*2 means we have got an answer, add this subset to list;

2. left bracket number<n, means we can still add another left bracket to the subset;

3. right bracket number<left bracket, means we can still add another right bracket to the subset;

follow this rule to do backtracking.

class Solution {    public List
     
       generateParenthesis(int n) {        List
      
        list=new ArrayList<>();        if(n==0) return list;        generate(list, "", n, 0, 0);        return list;    }    public void generate(List
       
         list, String str, int n, int nleft, int index){        if(index>=2*n){            list.add(str);return;        }        if(nleft