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

namespace _16.SubsetWithSum_S
{
    class Program
    {

        /* Problem 16.* Subset with sum S
         * 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.
            input array 	            S 	    result
            2, 1, 2, 4, 3, 5, 2, 6 	    14 	    yes
         */

        static int wantedSum;
        static bool solution = false;

        static void GenerateSubset(int[] arr, int[] subset, int index, int current, int elementsInSubset)
        {
            if (index == elementsInSubset)
            {
                CheckSubsets(subset, elementsInSubset);
                return;
            }

            for (int i = current; i < arr.Length; i++)
            {
                subset[index] = arr[i];
                GenerateSubset(arr, subset, index + 1, i + 1, elementsInSubset);
            }
        }

        static void CheckSubsets(int[] subset, int elementsInSubset)
        {
            int sum = 0;
            for (int i = 0; i < elementsInSubset; i++)
            {
                sum += subset[i];
            }
            if (sum == wantedSum)
            {
                for (int i = 0; i < elementsInSubset; i++)
                {
                    Console.Write("{0} ", subset[i]);
                }
                Console.WriteLine();
                solution = true;
            }
        }

        static void Main()
        {
            Console.Write("Enter number of elements: ");
            int n = int.Parse(Console.ReadLine());
            int[] arr = new int[n];
            for (int index = 0; index < n; index++)
            {
                Console.Write("Enter element {0}: ", index);
                arr[index] = int.Parse(Console.ReadLine());
            }
            Console.Write("Enter sum S: ");
            wantedSum = int.Parse(Console.ReadLine());

            int[] subset = new int[n];
            for (int elementsInSubset = 1; elementsInSubset <= n; elementsInSubset++)
            {
                GenerateSubset(arr, subset, 0, 0, elementsInSubset);
            }

            if (!solution)
            {
                Console.WriteLine("Ain't no subset with sum {0}.", wantedSum);
            }
        }
    }
}
