Given the values x1,...,xn of the n different scores, and a number k, determine whether k is a possible sum of any combination of scores

gistfile1.cs

    internal class Program
    {
        private static void Main( string[] args )
        {
            var source = new long[] { 8, 4, 2 };
            Console.WriteLine( SolveMemoizedWithUtil( source, 23427 ) );
            Console.ReadLine();
        }

        public static bool Solve( IEnumerable<long> items, long target )
        {
            if ( target < 0 )
            {
                return false;
            }
            return target == 0 || items.Select( item => Solve( items, target - item ) ).Any( result => result );
        }

        public static bool SolveExpanded( IEnumerable<long> items, long target )
        {
            if ( target < 0 )
            {
                return false;
            }
            if ( target == 0 )
            {
                return true;
            }
            foreach ( long item in items )
            {
                bool result = Solve( items, target - item );
                if ( result )
                {
                    return true;
                }
            }
            return false;
        }

        public static bool SolveMemoized( IEnumerable<long> items, long value )
        {
            var cache = new Dictionary<long, bool>();
            Func<long, bool> action = null;
            action = target =>
                     {
                         if ( target < 0 )
                         {
                             return false;
                         }
                         if ( target == 0 )
                         {
                             return true;
                         }
                         bool result;
                         if ( cache.TryGetValue( target, out result ) )
                         {
                             return result;
                         }
                         foreach ( long item in items )
                         {
                             result = action( target - item );
                             if ( result )
                             {
                                 return true;
                             }
                         }
                         cache.Add( target, false );
                         return false;
                     };
            return action( value );
        }

        public static bool SolveMemoizedWithUtil( IEnumerable<long> items, long value )
        {
            Func<long, bool> action = null;
            action = target =>
                     {
                         if ( target < 0 )
                         {
                             return false;
                         }
                         if ( target == 0 )
                         {
                             return true;
                         }
                         foreach ( long item in items )
                         {
                             bool result = action( target - item );
                             if ( result )
                             {
                                 return true;
                             }
                         }
                         return false;
                     };
            action = Memoize( action );
            return action( value );
        }

        public static Func<TInput, TOutput> Memoize<TInput, TOutput>(Func<TInput, TOutput> source)
        {
            var cache = new Dictionary<TInput, TOutput>();
            return input =>
            {
                TOutput output;
                if (cache.TryGetValue(input, out output))
                {
                    return output;
                }
                output = source(input);
                cache.Add(input, output);
                return output;
            };
        }
    }