프로그래머스 - 타겟 넘버 (C#)

문제 설명

정수형 배열 numbers를 순서를 바꾸지 않고 +, - 해서 target이 만들어지는 방법이 몇 개인지 구하는 문제입니다.

문제 풀이

numbers가 { 1, 2, 3 } 이라면

+1 + 2 + 3
+1 + 2 - 3
+1 - 2 + 3
+1 - 2 - 3
-1 + 2 + 3
-1 + 2 - 3
-1 - 2 + 3
-1 - 2 - 3

해서 총 2 x 2 x 2 = 8개의 결과값이 나옵니다.
그 결과값 중 target과 같은 값의 개수를 구하면 됩니다.

재귀함수로 target을 찾는 방법으로 풀 수 있습니다.

재귀함수가 어떤 식으로 동작해야 target을 구할 수 있는지 생각해보면
재귀함수에 어떤 파라미터가 필요한지 알 수 있습니다.

제출 코드

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);
        }
    }
}