典型90問 002 Encyclopedia of Parentheses（★3）

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            //()
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            //(())
            //()()
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10");
            //((((()))))
            //(((()())))
            //(((())()))
            //(((()))())
            //(((())))()
            //((()(())))
            //((()()()))
            //((()())())
            //((()()))()
            //((())(()))
            //((())()())
            //((())())()
            //((()))(())
            //((()))()()
            //(()((())))
            //(()(()()))
            //(()(())())
            //(()(()))()
            //(()()(()))
            //(()()()())
            //(()()())()
            //(()())(())
            //(()())()()
            //(())((()))
            //(())(()())
            //(())(())()
            //(())()(())
            //(())()()()
            //()(((())))
            //()((()()))
            //()((())())
            //()((()))()
            //()(()(()))
            //()(()()())
            //()(()())()
            //()(())(())
            //()(())()()
            //()()((()))
            //()()(()())
            //()()(())()
            //()()()(())
            //()()()()()
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        if (N % 2 == 1) {
            return;
        }

        char[] CharArr = new char[] { '(', ')' };

        var Query = RubyPatternClass<char>.RepeatedPermutation(CharArr, N);

        var AnswerList = new List<string>();
        foreach (char[] EachArr in Query) {
            int StackCnt = 0;
            bool IsNG = false;
            for (int I = 0; I <= EachArr.GetUpperBound(0); I++) {

                if (EachArr[I] == '(') {
                    StackCnt++;
                }
                if (EachArr[I] == ')') {
                    if (StackCnt == 0) {
                        IsNG = true;
                        break;
                    }
                    StackCnt--;
                }
            }
            if (IsNG == false && StackCnt == 0) {
                AnswerList.Add(new string(EachArr));
            }
        }
        AnswerList.Sort();
        AnswerList.ForEach(pX => Console.WriteLine(pX));
    }
}

#region RubyPatternClass
// Rubyの場合の数
internal static class RubyPatternClass<Type>
{
    // 重複順列を返す
    private struct JyoutaiDef_RepeatedPermutation
    {
        internal List<int> SelectedIndList;
    }
    internal static IEnumerable<Type[]> RepeatedPermutation(IEnumerable<Type> pEnum, int pR)
    {
        if (pR == 0) yield break;
        Type[] pArr = pEnum.ToArray();

        var Stk = new Stack<JyoutaiDef_RepeatedPermutation>();
        JyoutaiDef_RepeatedPermutation WillPush;
        for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
            WillPush.SelectedIndList = new List<int>() { I };
            Stk.Push(WillPush);
        }

        while (Stk.Count > 0) {
            JyoutaiDef_RepeatedPermutation Popped = Stk.Pop();

            // クリア判定
            if (Popped.SelectedIndList.Count == pR) {
                var WillReturn = new List<Type>();
                Popped.SelectedIndList.ForEach(X => WillReturn.Add(pArr[X]));
                yield return WillReturn.ToArray();
                continue;
            }

            for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
                WillPush.SelectedIndList = new List<int>(Popped.SelectedIndList) { I };
                Stk.Push(WillPush);
            }
        }
    }
}
#endregion

解説

重複順列を列挙してから、バランスの取れた括弧かをチェックしてます。