// REMEMBER IF YOU WANT ALL COMBOS DON'T USE THE LAST COUNT "prvend", i.e. USE ALL ITEMS WHEN BUILDING YOUR LIST, FOR UNIQUE COMBOS USE LAST COUNT i.e. "prvend"

// bfs_balanced_parenthesis

using System;

using System.Collections.Generic;

​

public class paren

{

    public string res;

    public int lct;

    public int rct;

    int pcount;

    public paren(string s, int x, int l, int r)

    {

        pcount=x;

        res=s;

        lct=l;

        rct=r;

    }

    public bool addL()

    {

        if(lct>=pcount) return false;

        else

        {

            res+="(";

            lct++;

        }

        return true;

    }

    public bool addR()

    {

        if(res.Length==0) return false;

        if(rct>=lct) return false;

        if(rct>=pcount) return false;

        else

        {

            res+=")";

            rct++;

        }

        return true;

    }

}

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int np = 3;

        List<paren> ls = new List<paren>();

        ls.Add(new paren("", np, 0, 0));

        bool loop=true;

        int prvend=0;

        while(loop)

        {

            int n = ls.Count;

            for(int j=prvend;j<n;j++)

            {

                paren p = new paren(ls[j].res, np, ls[j].lct, ls[j].rct);

                if(p.addL()) ls.Add(p);

                paren q = new paren(ls[j].res, np, ls[j].lct, ls[j].rct);

                if(q.addR()) ls.Add(q);

                if(p.rct==np && p.lct==np) loop = false;

            }

            prvend = n;

        }

        foreach(paren p in ls)

        {

            if(p.lct==np && p.rct==np)

                Console.WriteLine(p.res + " " + p.lct + " " + p.rct);

        }

    }

}