07.SortedSubsetSums

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

class SortSubsetSums
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        List<int> numbers = Console.ReadLine().Split(' ').Select(int.Parse).Distinct().ToList();

        int subsetsNumber = 1 << numbers.Count;

        List<List<int>> allSets = new List<List<int>>();
        List<int> singleSubset = new List<int>();
        List<List<int>> sortedByCount = new List<List<int>>();

        allSets = CreateSubsets(subsetsNumber, numbers, allSets, singleSubset);

        foreach (List<int> l in allSets.Where(x => x.Sum() == n && x.Count > 0))
        {
            sortedByCount.Add(l);
        }

        if (sortedByCount.Count == 0)
        {
            Console.WriteLine("No matching subsets.");
        }
        else
        {
            PrintSums(sortedByCount, n);
        }
    }

    static List<List<int>> CreateSubsets(int subsetsNumber, List<int> numbers, List<List<int>> allSets, List<int> singleSubset)
    {
        for (int i = 0; i < subsetsNumber; i++)
        {
            int pos = numbers.Count - 1;
            int bitmask = i;

            while (bitmask > 0)
            {
                if ((bitmask & 1) == 1)
                {
                    singleSubset.Add(numbers[pos]);
                }
                bitmask >>= 1;
                pos--;
            }
            singleSubset.Sort();
            allSets.Add(new List<int>(singleSubset));
            singleSubset.Clear();
        }
        return allSets;
    }

    static void PrintSums(List<List<int>> uniqueElements, int n)
    {
        IEnumerable<List<int>> query = uniqueElements.OrderBy(l => l.Count).ThenBy(l => l[0]);

        foreach (List<int> list in query)
        {
            foreach (int num in list)
            {
                if (list.IndexOf(num) < list.Count - 1)
                {
                    Console.Write(num + " + ");
                }
                else
                {
                    Console.Write(num);
                }
            }
            Console.WriteLine(" = {0}", n);
        }
    }
}