class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
		//As generated string would have size 2n
        backtrack("",0,0,result,2*n);
        return result;
    }

    private void backtrack(String res,int open,int close,List<String> result,int n){
	   // Make sure open braces are not greater than n/2
        if(open > n/2)
            return;
		//Make sure closed braces or not greater than open
        if(close > open)
            return;
		//when reached required size add to result
        if(res.length()==n){
            result.add(res);
            return;
        }
		//call function recursively with adding open and close one by one
        backtrack(res + "(",open+1,close,result,n);
        backtrack(res + ")",open,close+1,result,n);

    }
}