using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    private static readonly Operator[] Operators = new Operator[] { new AddOperator(), new SubtractOperator(), new MultiplyOperator(), new DivideOperator(), new NullOperator() };

    public static void Main()

    {

        var numbers = new[] { 50, 100, 5, 7, 3 };

        var target = 500;

        var stack = new Stack<AttemptState>();

        stack.Push(new AttemptState(ImmutableStack<int>.Empty, ImmutableStack<string>.Empty, numbers));

        while (stack.Count > 0)

        {

            // Add a number, apply an operator. If it matches, boom! It there are numbers left, push it

            var attempt = stack.Pop();

            foreach (var remainingNumber in attempt.RemainingNumbers)

            {

                var attemptStack = attempt.Stack.Push(remainingNumber);

                var history = attempt.History.Push(remainingNumber.ToString());

                foreach (var op in Operators)

                {

                    var operatedStack = op.TryApply(attemptStack);

                    if (operatedStack != null)

                    {

                        history = history.Push(op.Name);

                        if (operatedStack.Count == 1 && operatedStack.Top == target)

                        {

                            Console.WriteLine("GOT ONE");

                            Console.WriteLine(String.Join(", ", history.Reverse()));

                        }

                        else if (attempt.RemainingNumbers.Length > 1)

                        {

                            stack.Push(new AttemptState(operatedStack, history, attempt.RemainingNumbers.Except(new[] { remainingNumber }).ToArray())); 

                        }

                    }

                }

            }

        }

    }

    public static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> input)

    {

        if (!input.Any())

            yield break;

        foreach (var first in input)

        {

            var firstList = new[] { first };

            foreach (var permutation in Permutations(input.Except(firstList)))

            {

                yield return firstList.Concat(permutation); 

            }

        }

    }

}

​

public struct AttemptState

{

    public readonly ImmutableStack<int> Stack;

    public readonly ImmutableStack<string> History;

    public readonly int[] RemainingNumbers;

​

    public AttemptState(ImmutableStack<int> stack, ImmutableStack<string> history, int[] remainingNumbers)

    {

        this.Stack = stack; 

        this.History = history;

        this.RemainingNumbers = remainingNumbers;

    }

}

​

​

public abstract class Operator

{

    public abstract string Name { get; }

    public virtual ImmutableStack<int> TryApply(ImmutableStack<int> stack)

    {

        if (stack.Count < 2)

            return null;

        var a = stack.Top;

        stack = stack.Pop();

        var b = stack.Top;

        stack = stack.Pop();

        int result;

        if (this.Operate(a, b, out result))

            return stack.Push(result);

        else

            return null;

    }

    protected abstract bool Operate(int a, int b, out int result);

}

​

​

public class AddOperator : Operator

{

    public override string Name { get { return "+"; } }

    protected override bool Operate(int a, int b, out int result)

    {

        result = a + b;

        return true;    

    }

}

​

public class SubtractOperator : Operator

{

    public override string Name { get { return "-"; } }

    protected override bool Operate(int a, int b, out int result)

    {

        result = a - b;

        return result > 0;

    }

}

​

public class MultiplyOperator : Operator

{

    public override string Name { get { return "*"; } }

    protected override bool Operate(int a, int b, out int result)

    {

        result = a * b;

        return true;

    }

}

​

public class DivideOperator : Operator

{

    public override string Name { get { return "/"; } }

    protected override bool Operate(int a, int b, out int result)

    {

        result = 0;

        if (b > a || (a % b) != 0)

            return false;

        result = a / b;

        return true;

    }

}

​

public class NullOperator : Operator

{

    public override string Name { get { return ""; } }

    public override ImmutableStack<int> TryApply(ImmutableStack<int> stack)

    {

        return stack;

    }

    protected override bool Operate(int a, int b, out int result)

    {

        throw new NotImplementedException();

    }

}

​

public abstract class ImmutableStack<T> : IEnumerable<T>

{

    public static readonly ImmutableStack<T> Empty = new EmptyStack();

    public abstract T Top { get; }

    public abstract int Count { get; }

    public bool IsEmpty { get { return this.Count == 0; } }

    public ImmutableStack<T> Push(T item)

    {

        return new NonEmptyStack(item, this);   

    }

    public IEnumerator<T> GetEnumerator()

    {

        for (var current = this; !current.IsEmpty; current = current.Pop())

        {

            yield return current.Top;

        }

    }

    IEnumerator IEnumerable.GetEnumerator()

    {

        return this.GetEnumerator();    

    }

    public abstract ImmutableStack<T> Pop();

    private class EmptyStack : ImmutableStack<T>

    {

        public override T Top { get { throw new InvalidOperationException("An empty stack has no top"); } }

        public override int Count { get { return 0; } }

        public override ImmutableStack<T> Pop() { throw new InvalidOperationException("Cannot pop an empty stack"); }

    }

    private class NonEmptyStack : ImmutableStack<T>

    {

        private readonly T head;

        private readonly ImmutableStack<T> tail;

        private readonly int count;

        public override T Top { get { return this.head; } }

        public override int Count { get { return this.count; } }

        public NonEmptyStack(T head, ImmutableStack<T> tail)

        {

            this.head = head;

            this.tail = tail;

            this.count = tail.Count + 1;

        }

        public override ImmutableStack<T> Pop()

        {

            return this.tail;   

        }

    }

}