Given digits less and equal than 9, find expression using +, - to match given target. March 21, 2022

GivenSumFindExpression.cs

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

namespace given_target_sum
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Program();
            var result = test.buildExpression("123456789", 100);
        }

        /// <summary>
        /// 123456789 = 100 (also known as targetSum)
        /// Using standard integer arithmetic operators +, -, how many different solutions 
        /// can you find by inserting the operators between some digits?
        /// All combinations that sums up to 100:
        /// -1+2-3+4+5+6+78+9 = 100
        /// 1+2+3-4+5+6+78+9 = 100
        /// 1+2+34-5+67-8+9
        /// 1+23-4+5+6+78-9
        /// 1+23-4+56+7+8+9
        /// </summary>
        /// <param name="digits"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public List<string> buildExpression(string digits, int target)
        {
            if (digits == null || digits.Length == 0)
            {
                return new List<string>();
            }

            var lists = new List<string>();
            var list = new List<string>();

            runDFS(digits, 0, lists, list, 0, target);
            return lists;
        }
         
        /// <summary>
        /// Given digits.Length <= 9
        /// Three bugs in my performance:
        /// 1. len <= digits.Length - for loop, I should include =, otherwise nothing is found
        /// 2. base case: check index >= digits.Length condition, return
        /// 3. define nextRunningSum, otherwise runningSum need to restore the original value after runDFS call
        /// </summary>
        /// <param name="digits"></param>
        /// <param name="index"></param>
        /// <param name="lists"></param>
        /// <param name="list"></param>
        /// <param name="runningSum"></param>
        /// <param name="target"></param>
        private void runDFS(string digits, int index, List<string> lists, List<string> list, int runningSum, int target)
        {
            if (index >= digits.Length && runningSum == target)
            {
                lists.Add(string.Join("", list));  // -1+2-3+4+5+6+78+9
                return;
            }

            if (index >= digits.Length)
            {
                return;
            }
            
            for (int len = 1; len <= digits.Length - index; len++)  // bug catched: len < digits.Length
            {
                for (int op = 0; op < 2; op++)  // op = 0 +, op 1 -, missing ? 3
                {
                    var no = Convert.ToInt32(digits.Substring(index, len));
                    var nextRunningSum = runningSum;
                    if (op == 0)
                    {
                        nextRunningSum += no;
                    }
                    else
                    {
                        nextRunningSum -= no;
                    }

                    list.Add((op == 0 ? "+" : "-") + no.ToString());
                    runDFS(digits, index + len, lists, list, nextRunningSum, target);
                    list.RemoveAt(list.Count - 1);
                }
            }            
        }
    }
}