using System;

using System.Collections.Generic;

using System.Linq;

​

// В массиве объектов каждый объект имеет поля:

// * values - набор "купюр" разных номиналов > 0, номиналы могут повторятся

// * target - сумма которую необходимо набрать используя купюры из values

// 

// Нужно модифицировать метод Process который занимается обработкой каждого набора, он должен возвращать:

// * массив купюр которые в сумме составят необходимое значение

// * null если из указанных купюр получить нужную сумму невозможно

// 

// В случае наличия нескольких вариантов для получения суммы без сдачи, в качестве ответа может быть указан любой.

​

​

namespace Sample {

    public class Program {

        public static void Main(string[] args) {

            var data = new [] {

                        new { target = 100, values = new [] { 100 } },

                        new { target = 100, values = new [] { 50,70,120,150 } },

                        new { target = 12, values = new [] { 1,9,7,3,5 } },

                        new { target = 30, values = new [] { 1,2 } },

                        new { target = 30, values = new [] { 60,15,9,9,9,8,8,5,5,3,3,3,3,3,2,2,2,1 } },

                        new { target = 2147483647, values = new [] { 2147483500,100,40,5,1,1,1,1 } },

                        new { target = 100, values = new [] { 100,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 } },

                        new { target = 100, values = new [] { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 } },

                        new { target = 50, values = new [] { 49,47,30,15,10,10 } }

                       };

            foreach(var item in data) {

                var result = Process(item.target, item.values);

                var resultStr = result == null ? "NO" : String.Join(", ",  result);

                Console.WriteLine(item.target + " " + resultStr);

            }

        }

        private static IEnumerable<int> Process(int target, int[] values) {

            var sorted = values.OrderByDescending(i => i).Where(i => i <= target).ToArray();

            var stack = new Stack<int>();

            var index = 0;

            while (stack.Count != sorted.Length) {

                for (; index < sorted.Length; index++) {

                    stack.Push(index);

                    var sum = stack.Select(s => values[s]).Sum();

                    if (sum == target) return stack.Select(s => sorted[s]);

                    if (sum > target) {

                        stack.Pop();

                        continue;

                    }

                }

                if (stack.Count == 0) break;

                index = stack.Pop() + 1;

            }

            return null;

        }

    }

}