import java.util.* ;

import java.io.*; 

public class Solution {

    public static ArrayList<String> validParenthesis(int n){

     ArrayList<String> st=new ArrayList<>();

     StringBuilder s=new StringBuilder();

           helper(n,n,st,s);

           return st;

    } 

    public static void helper(int left,int right,ArrayList<String> list,StringBuilder st)

    {

        if(left==0&&right==0)

        {

            list.add(st.toString());

            return;

        }

        if(left<0||right<0||left>right)

            return;

        helper(left-1,right,list,st.append('('));

        st.deleteCharAt(st.length()-1);

        helper(left,right-1,list,st.append(')'));

        st.deleteCharAt(st.length()-1);

    }

}