06.FindSubsetSums

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());
    string[] inputNums = Console.ReadLine().Split(' ');

    List<int> numbers = new List<int>();


    for (int i = 0; i < inputNums.Length; i++)
    {
        numbers.Add(int.Parse(inputNums[i]));
    }

    int subsetsNumber = (int)Math.Pow(2, numbers.Count);

    HashSet<List<int>> allSets = new HashSet<List<int>>();
    List<int> subset = new List<int>();


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


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

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

    }
}