using System;

​

namespace algorithm_simple_csharp

{

    class Program

    {

        static void Main(string[] args)

        {

            Console.WriteLine("Working on it!");

​

            int[] allNumbers = new int[] {1,2,3,4,5,6,7,8};

            int desiredSum = 0;

            int initIndex = 0;

            // Start the recursion          

            int totalSum = ApplyNumber(0, initIndex, desiredSum, "", allNumbers);

            Console.WriteLine("Solutions " + totalSum);

        }

​

        static int ApplyNumber(int currentSum, int index, int desiredSum, string currentChain, int[] allNumbers)

        {

            if(index > allNumbers.GetUpperBound(0))

            {

                if(currentSum == desiredSum)

                {

                    Console.WriteLine(currentChain);

                    return 1;

                }

                return 0;

            }

            // Following the +

            int newSum = currentSum + allNumbers[index];

            string newChain = currentChain + " + " + allNumbers[index];

            int solutions = ApplyNumber(newSum, index + 1, desiredSum, newChain, allNumbers);

            // Following the -

            newSum = currentSum - allNumbers[index];

            newChain = currentChain + " - " + allNumbers[index];

            solutions += ApplyNumber(newSum, index + 1, desiredSum, newChain, allNumbers);  

            return solutions;

        }

​

    }

​

}