C# 타겟 넘버(DFS)

using System;
using System.Collections;
using System.Collections.Generic;

public class Solution 
{
    List<int> result;
    
    public int solution(int[] numbers, int target) 
    {
        int answer = 0;
        result = new List<int>();     
        FindTarget(numbers, 0, target, 0);
        
        for (int i = 0; i < result.Count; i++)
        {
            if (result[i] == target) answer++;
        }
        
        return answer;
    }
    
    public void FindTarget(int[] numbers, int index, int targetNumber, int currentValue)
    {
        if (index == numbers.Length)
        {
            result.Add(currentValue);
        }
        else
        {
            int currentValue1 = currentValue + numbers[index];
            FindTarget(numbers, index + 1, targetNumber, currentValue1);
            int currentValue2 = currentValue - numbers[index];
            FindTarget(numbers, index + 1, targetNumber, currentValue2);
        }
    }
}

 

////

 

using System;

public class Solution {
    static int Dfs(int[] arr, int target, int idx, int num)
    {
        if (idx == arr.Length)
        {
            if (target == num) 
            	return 1;
            else 
            	return 0;
        }
        else
            return Dfs(arr, target, idx + 1, num + arr[idx]) + Dfs(arr, target, idx + 1, num - arr[idx]);
    }

    public int solution(int[] numbers, int target) {
        int answer = 0;
        return Dfs(numbers, target, 0, 0);
    }
}