LeetCode: Generate Parentheses

Generate Parentheses


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

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<Integer> diff = new ArrayList<Integer>();
        res.add("");
        diff.add(0);
        
        
        for(int i=0;i<2*n;i++){
            ArrayList<String> temp1 = new ArrayList<String>();
            ArrayList<Integer> temp2 = new ArrayList<Integer>();
            for(int j=0;j<res.size();j++){
                String s = res.get(j);
                int k = diff.get(j);   
                if(i<2*n-1){
                    temp1.add(s+"(");
                    temp2.add(k+1);
                }
                if(k>0 && i<2*n-1 || k==1 && i==2*n-1){
                    temp1.add(s+")");
                    temp2.add(k-1);
                }
            }
            res = new ArrayList<String>(temp1);
            diff = new ArrayList<Integer>(temp2);
        }
        
        return res;
    }
}