using System;

using System.Collections.Generic; // Import the Dictionary class

/*

    Write a function that, given an array of unique numbers and a target number,

    Will return true if there is a combination of numbers from the array that add up to the target

*/

public class Program

{

    static bool CanSumHelper(int[] candidates, int target)

    {

        // Create a memoization dictionary to store intermediate results

        Dictionary<int, bool> memo = new Dictionary<int, bool>();

​

        // Helper function to recursively check if the target can be achieved

        bool CanSumHelper(int currentTarget)

        {

            // If the current target is zero, we have found a combination

            if (currentTarget == 0)

                return true;

​

            // If the current target is negative, it cannot be achieved

            if (currentTarget < 0)

                return false;

​

            // Check if we have already computed the result for the current target

            if (memo.ContainsKey(currentTarget))

                return memo[currentTarget];

​

            // Try each candidate number to see if it can lead to a valid combination

            foreach (int candidate in candidates)

            {

                int newTarget = currentTarget - candidate;

                if (CanSumHelper(newTarget))

                {

                    // Store the result in the memoization dictionary and return true

                    memo[currentTarget] = true;

                    return true;

                }

            }

​

            // If none of the candidates lead to a valid combination, store the result as false

            memo[currentTarget] = false;

            return false;

        }

​

        return CanSumHelper(target);

    }

    public static void check(int[] candidates, int target, bool expected) 

    {

        bool result = CanSumHelper(candidates, target);

        Console.WriteLine(candidates + (expected ? " HAS " : " DOES NOT HAVE ") + target + " = " + (result == expected));

    }

​

    public static void Main()

    {

        check(new int[] { 2, 7, 6, 3 }, 18, true);

        check(new int[] { 2, 1, 7, 6, 3}, 18, true);

        check(new int[] { 2, 7, 6, 1, 3 }, 18, true);

        check(new int[] { 2, 7, 6, 3, 1 }, 18, true);

        check(new int[] { 1, 2, 7, 6, 3 }, 18, true);

        check(new int[] { 2, 7, 8, 3 }, 9, true);

        check(new int[] { 2, 7, 8, 3 }, 10, true);

        check(new int[] { 2, 7, 8, 3 }, 5, true);

        check(new int[] { 2, 7, 8, 3 }, 15, true);

        check(new int[] { 2, 7, 8, 3 }, 11, true);

        check(new int[] { 2, 7, 8, 3 }, 1, false);

        check(new int[] { 2, 7, 8, 3 }, 4, false);

        check(new int[] { 2, 7, 8, 3 }, 6, false);

        check(new int[] { 2, 7, 8, 3 }, 14, false);

        check(new int[] { 2, 7, 8, 3 }, 16, false);

        check(new int[] { 2, 7, 8, 3 }, 19, false);

    }

}

​