07.SortedSubsetSums

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortedSubsetSums
{
    class SortedSubsetSums
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split(' ');
            int[] arr = new int[input.Length];
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = int.Parse(input[i]);
            }
            arr = arr.Distinct().ToArray();
            Array.Sort(arr);
            List<int> tempSubset = new List<int>();
            List<List<int>> matchedSubsets = new List<List<int>>();
            int combinations = 1 << arr.Length;
            bool noSubsets = false;
            for (int i = 1; i < combinations; i++)
            {
                for (int j = 0; j < arr.Length; j++)
                {
                    int mask = i & (1 << j);
                    if (mask != 0)
                    {
                        tempSubset.Insert(0, arr[arr.Length - 1 - j]);
                    }
                }
                if (tempSubset.Sum() == n)
                {
                    matchedSubsets.Insert(0, new List<int>(tempSubset));
                    noSubsets = true;
                }
                tempSubset = new List<int>();
            }
            var ordered = matchedSubsets.OrderBy(x => x.Count);
            foreach (var item in ordered)
            {
                Console.WriteLine("{0} = {1}",string.Join(" + ",item),n);
            }
            if (!noSubsets)
            {
                Console.WriteLine("No matching subsets.");
            }
        }
    }
}