Pr07SortedSubsetSums

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

// Modify the program you wrote for the previous problem to print the results in the following way:
// each line should contain the operands (numbers that form the desired sum) in ascending order;
// the lines containing fewer operands should be printed before those with more operands;
// when two lines have the same number of operands, the one containing the smallest operand should be printed first.
// If two or more lines contain the same number of operands and have the same smallest operand,
// the order of printing is not important.

namespace Pr07SortedSubsetSums
{
    class Pr07SortedSubsetSums
    {
        static void Main(string[] args)
        {
            int sum = int.Parse(Console.ReadLine());
            int[] nums = Console.ReadLine().Split(' ').Select(n => int.Parse(n)).Distinct().ToArray();
            int numsLength = nums.Length;
            List<int> subset = new List<int>();
            List<string> subsetStrings = new List<string>();
            bool isMatch = false;
            int combos = 1 << numsLength;
            for (int mask = 0; mask < combos; mask++)
            {
                int subsetSum = int.MinValue + 2;
                for (int i = 0; i < numsLength; i++)
                {
                    if ((mask & (1 << i)) != 0)
                    {
                        if (subsetSum == int.MinValue + 2)
                        {
                            subsetSum = 0;
                        }
                        subset.Add(nums[i]);
                        subsetSum += nums[i];
                    }
                }
                if (subsetSum == sum)
                {
                    subsetStrings.Add(string.Join(" + ", subset) + " = " + sum);
                    isMatch = true;
                }
                subset.Clear();
            }
            if (isMatch == false)
            {
                Console.WriteLine("No matching subsets.");
            }
            else
            {
                foreach (string subsetString in SortByLength(subsetStrings))
                {
                    Console.WriteLine(subsetString);
                }
            }
        }

        static IEnumerable<string> SortByLength(List<string> subsetStrings)
        {
            var sorted = from s in subsetStrings orderby s.Length ascending select s;
            return sorted;
        }
    }
}