B18 Subset Sum with Restoration

問題へのリンク

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("3 7");
            WillReturn.Add("2 2 3");
            //3
            //1 2 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 10");
            WillReturn.Add("1 2 4");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 100");
            WillReturn.Add("14 23 18 7 11 23 23 5 8 2");
            //6
            //2 3 6 7 8 9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mS;
    static int[] mAArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mS = wkArr[1];

        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        ExecDFS();
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal int CurrSum;
        internal string Path;
    }

    static void ExecDFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.CurrSum = 0;
        WillPush.Path = "";
        Stk.Push(WillPush);

        // 最小Ind[和]なDict
        var MemoDict = new Dictionary<int, int>();

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

            if (Popped.CurrSum == mS) {
                string[] SplitArr = Popped.Path.Split(',');
                Console.WriteLine(SplitArr.Length);
                Console.WriteLine(string.Join(" ", SplitArr));
                return;
            }

            for (int I = Popped.CurrInd; I <= mAArr.GetUpperBound(0); I++) {
                WillPush.CurrInd = I + 1;
                WillPush.CurrSum = Popped.CurrSum + mAArr[I];

                if (MemoDict.ContainsKey(WillPush.CurrSum)) {
                    if (MemoDict[WillPush.CurrSum] <= WillPush.CurrInd) {
                        continue;
                    }
                }
                MemoDict[WillPush.CurrSum] = WillPush.CurrInd;

                if (Popped.Path == "") {
                    WillPush.Path = (I + 1).ToString();
                }
                else {
                    WillPush.Path = Popped.Path + "," + (I + 1).ToString();
                }
                Stk.Push(WillPush);
            }
        }

        Console.WriteLine(-1);
    }
}

解説

DFSで解いてます。
枝切り用で、最小Ind[和]なDictを持ってます。