6.SubsetSums

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

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

        List<List<int>> allSets = GenerateSubsets(numbers);
        List<List<int>> goodSets = GetGoodSubsets(allSets, n);
        PrintSubsets(goodSets, n);
    }

    static List<List<int>> GenerateSubsets(List<int> inputNumbers)
    {
        List<List<int>> allCombinations = new List<List<int>>();
        List<int> subset = new List<int>();
        int subsetsNumber = 1 << inputNumbers.Count;

        for (int i = 1; i < subsetsNumber; i++)
        {
            int pos = inputNumbers.Count - 1;
            int bitmask = i;

            while (bitmask > 0)
            {
                if ((bitmask & 1) == 1)
                {
                    subset.Add(inputNumbers[pos]);
                }
                bitmask >>= 1;
                pos--;
            }
            allCombinations.Add(new List<int>(subset));
            subset.Clear();
        }
        return allCombinations;
    }

    static List<List<int>> GetGoodSubsets(List<List<int>> allCombinations, int number)
    {
        List<List<int>> properSets = new List<List<int>>();

        foreach (List<int> list in allCombinations)
        {
            if (list.Sum() == number)
            {
                properSets.Add(list);
            }
        }
        return properSets;
    }

    static void PrintSubsets(List<List<int>> properSubsets, int number)
    {
        if (properSubsets.Count == 0)
        {
            Console.WriteLine("No matching subsets.");
        }
        else
        {
            foreach (List<int> subset in properSubsets)
            {
                foreach (int num in subset)
                {
                    if (subset.IndexOf(num) != subset.Count - 1)
                    {
                        Console.Write(num + " + ");
                    }
                    else
                    {
                        Console.Write(num);
                    }
                }
                Console.WriteLine(" = {0}", number);
            }
        }
    }
}