<Hard> Expression Add Operators (LeetCode : C#)

https://leetcode.com/problems/expression-add-operators/

📕 문제 설명

더하기 빼기 곱하기 연산자 숫자들 사이에 넣어서 target value 만들 수 있는 경우의 수 반환

• Input
  숫자로 이루어진 문자열 (string), target 값 (int)
• Output
  연산자 추가해서 target value 만들 수 있는 경우의 수

예제

풀이

dfs 사용한 풀이. 숫자를 해당 index부터 해서 자리수 다양하게 해가면서 +, -, * 적용시켜보는 방식

public class Solution
{
    List<int> nums = new();
    HashSet<string> answer = new HashSet<string>();
    int n = 0;
    public IList<string> AddOperators(string num, int target)
    {
        foreach (char c in num) nums.Add(Int32.Parse(c.ToString()));
        n = nums.Count;
        Calculate(0, target, "", 0, 0);
        return answer.ToList();
    }

    private void Calculate(int index, int target, string exp, long total, long prev)
    {
        if (index == n && total == target) 
        {
            answer.Add(exp);
            return;
        }
        
        long number = 0;
        string subExp = "";

        for (int i = index; i < n; i++)
        {
            subExp += nums[i];
            number = number * 10 + nums[i];
            if (subExp.Length > 1 && subExp[0] == '0') return; // 십의 자리 이상인데 제일 앞 0오는 경우 pass
            if (index == 0) Calculate(i + 1, target, $"{subExp}", number, number);
            else
            {

                Calculate(i + 1, target, $"{exp}+{subExp}", total + number, number);
                Calculate(i + 1, target, $"{exp}-{subExp}", total - number, -number);
                // 곱셈은 연산자 순서 고려해야해서 prev 필요함 
                Calculate(i + 1, target, $"{exp}*{subExp}", total - prev + prev * number, prev * number);

            }
        }

    }
}

결과