282 Expression Add operators - C# solution | DFS | * high precedence above +/- |

282ExpressionAddOperators.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _282_expression_add_operators_III
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Program();
            var result = test.AddOperators("123", 6); 
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="num"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public IList<string> AddOperators(string num, int target)
        {
            var result = new List<string>();

            runDFS(result, "", 0, 0, num, target);

            return result;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="result"></param>
        /// <param name="expression"></param>
        /// <param name="number1"></param>
        /// <param name="number2"></param>
        /// <param name="digit"></param>
        /// <param name="target"></param>
        private void runDFS(IList<string> result, string expression, long number1, long number2, string digits, long target)        
        {
            if (digits.Length == 0)
            {
                if(target - number1 - number2 == 0)
                {
                    result.Add(expression);
                }

                return;
            }

            // integer 1 - 10 digits
            for (int i = 1; i < 11 && i <= digits.Length; i++)
            {
                var substring = digits.Substring(0, i);
                var rest = digits.Substring(i);

                long value = Convert.ToInt64(substring);

                if (value > int.MaxValue || number2 > int.MaxValue)
                {
                    break; 
                }

                if (expression.Length == 0)
                {
                    runDFS(result, substring, 0, value, rest, target);
                }
                else
                {
                    // keep * high precedence above +/-
                    // three DFS calls for */+/- 
                    // number1 + number2 * number3 -> number1 + (number2 * number3)
                    // number1 + number2 + number3 -> (number1 + number2) + number3                    
                    // number1 + number2 - number3 -> (number1 + number2) + (-1 * number3)
                    runDFS(result, expression + "*" + substring, number1, number2 * value, rest, target);
                    runDFS(result, expression + "+" + substring, number1 + number2, value, rest, target);
                    runDFS(result, expression + "-" + substring, number1 + number2, -value, rest, target); 
                }

                if (value == 0)
                {
                    break; // avoid result of "000"/"012" etc. 
                }
            }
        }
    }
}