/*16. * We are given an array of integers and a number S.
Write a program to find if there exists a subset of the elements of the array that has a sum S.
Example: arr={2, 1, 2, 4, 3, 5, 2, 6}, S=14  yes (1+2+5+6)*/

using System;

class FindSubsetSum
{
    static void Main()
    {
        int lengthOfArray = 10;
        int[] numbers = { 1, 5, 3, 2, 8, -2, 4, -1, 9, -5 };

        //Console.Write("Enter the length of array: ");
        //int lengthOfArray = int.Parse(Console.ReadLine());

        //int[] numbers = new int[lengthOfArray];
        //for (int i = 0; i < lengthOfArray; i++)
        //{
        //    numbers[i] = int.Parse(Console.ReadLine());
        //}

        Console.Write("Enter the value of the sum which we looking for: ");
        int sum = int.Parse(Console.ReadLine());

        int variation = (int)Math.Pow(2, lengthOfArray) - 1;
        int counter = 0;
        bool isConsist = false;

        for (int i = 1; i <= variation; i++)
        {
            string binaryI = Convert.ToString(i, 2).PadLeft(lengthOfArray, '0');
            long result = 0;
            string strResult = string.Empty;

            for (int j = 0; j < lengthOfArray; j++)
            {
                if (binaryI[j] == '1')
                {
                    result += numbers[j];
                    strResult += numbers[j] + " + ";
                }
            }

            if (result == sum)
            {
                isConsist = true;
                strResult = strResult.Remove(strResult.Length - 3);
                Console.WriteLine("[{0}], S = {1}  yes ({2})", string.Join(", ", numbers), sum, strResult);
                counter++;
            }
        }

        if (isConsist)
        {
            Console.WriteLine("Total: {0}", counter);
        }
        else
        {
            Console.WriteLine("[{0}], S = {1}  no", string.Join(", ", numbers), sum);
        }
    }
}