using System;

public class Program

{

    public static void Main()

    {

        int[] array = new[] {3, 34, 4, 12, 5, 2};

        int targetSum = 9;

        bool hasSubsetSum = HasSubsetSum(array, targetSum);

        string message = hasSubsetSum ? "Yes there is a subset with sum:"+targetSum : "There is no subset that sums up to:"+targetSum;

        Console.WriteLine(message);

    }

    private static bool HasSubsetSum(int[] array, int targetSum)

    {

        if(targetSum == 0)

            return true;

        else if(array == null || array.Length == 0)

            return false;

        // Each cell in the memory[i][j] represents one thing:

        // Can sum J be obtained by subset till I.

        // To obtain the answer to above we determine two things:

        // 1. Can sum J be obtained by EXCLUDING the element at I - answer is at memory[i-1][J]

        // 2. Can sum J be obtained by INCLUDING the element at I - answer is at remainingSum = J-array[i]; memory[i-1][remainingSum]

        bool[,] memory = new bool[array.Length+1, targetSum+1];

        // Sum 0 can be obtained by excluding all elements

        // So at every cell memory[i][0] the answer to Q2 above is TRUE.

        for(int i = 0;i < array.Length+1;i++)

        {

            memory[i, 0] = true;

        }

        // The first row 0th row means that not including any element in the array.

        // All the columns except 0th column will be false because you can not obtain any other sum from empty set except 0

        for(int i = 1;i < targetSum+1;i++)

        {

            memory[0, i] = false;

        }

        // Now for the rest of cells follow the logic described above.

        // Note that if the current element is greater than sum then we should not even consider including it. (Assuming all positive ints becasue negative ints can not be indexed)

        for(int i = 1; i < array.Length+1;i++)

        {

            for(int currentSum = 1; currentSum < targetSum+1;currentSum++)

            {

                int currentElement = array[i];

                if(currentElement > currentSum)

                {

                    // The only way here is to exclude current element, because if we include we will get negative index

                    memory[i, currentSum] = memory[i-1, currentSum];

                }

                else

                {

                    bool excludingCurrentElement = memory[i-1, currentSum];

                    int remainingSum = currentSum-currentElement;

                    bool includingCurrentElement = memory[i-1, remainingSum];

                    memory[i, currentSum] = excludingCurrentElement || includingCurrentElement;

                }

            }

        }

        return memory[array.Length, targetSum];

    }

}