using System;

using System.Linq;

using System.Collections.Generic;

using System.Diagnostics;

​

public class Program

{

    class AnswerFinder

    {

        public static int MaxLength = 4;

        public static int Sum = 15;

        public static int MinNumber = 1;

        public static int MaxNumber = 9;

        public static void Set(int maxLen, int sum, int min, int max)

        {

            MaxLength = maxLen;

            Sum = sum;

            MinNumber = min;

            MaxNumber = max;

        }

​

        public Stack<int> Digits = new Stack<int>();

        bool lastDigFixed = false;

        int delta = Sum;

        public int Min = MinNumber, Max = MaxNumber;

        public bool Perfect = false;

​

        int currSum = 0;

​

        private void updateStats(int sumChange)

        {

​

            currSum = currSum + sumChange;

​

            int currLen = Digits.Count; //目前組合的數字長度

            if (currLen == 0) return; //組合已無數字不需重算

            lastDigFixed = MaxLength - currLen == 1; //最後一位數確定

            delta = Sum - currSum; //目前總和與目標總和的差額

            Perfect = MaxLength == currLen && delta == 0; //是否符合要求

​

            //下個可用數字為為已使用數字之最大者＋1

            var nextNum = Digits.Peek() + 1;

            //若只剩一位且差額在可用數字範圍，以差額為Min；否則取下一可用數字

            Min = lastDigFixed && delta >= nextNum ? delta : nextNum;

​

            //若只剩一位且差額在可用數字範圍內，以差額為Max；否則取數字上限及差額較小者

            Max = lastDigFixed && delta <= MaxNumber ?

                  delta : Math.Min(MaxNumber, delta);

​

        }

​

        public void Push(int num)

        {

            Digits.Push(num); //將數字放進組合

            updateStats(num);

        }

​

        public void Pop()

        {

            int num = Digits.Pop(); //將數字從組合換下來

            updateStats(-num);

        }

​

        public List<string> Answers = new List<string>();

​

        public void Explore()

        {

            //下一位數字可用範圍為Min to Max

            int min = Min, max = Max;

            for (var n = min; n <= max; n++)

            {

                Push(n);

                if (Perfect)

                    Answers.Add(string.Join(", ", Digits.Reverse().ToArray()));

                else

                    Explore();

                Pop();

            }

            return;

        }

​

    }

​

    public static void Main(string[] args)

    {

        AnswerFinder.Set(4, 15, 1, 9);

        AnswerFinder.Set(8, 224, 1, 32);

        AnswerFinder t = new AnswerFinder();

        Stopwatch sw = new Stopwatch();

        sw.Start();

        t.Explore();

        sw.Stop();

        Console.WriteLine("Done! {0} answers found in {1:n0}ms.",

                          t.Answers.Count, sw.ElapsedMilliseconds);

        Console.WriteLine(string.Join("\n", t.Answers.ToArray()));

    }

}