타겟 넘버

[문제 Link] https://programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

총 2가지 방법이 있으므로, 2를 return 합니다.

로직

모든 경우를 DFS로 탐색하여 확인하여 모든 결과 값 중에 target 숫자가 된 경우의 수를 결과로 출력한다.

dfs 함수 생성. 입력값으로는 numbers 배열, 현재 계산 중인 index, target, 계산한 값이 들어간다.
dfs를 재귀로 계속 돌며, 현재 계산 중인 값이 배열의 마지막이면 target과 sum을 확인하여 같다면 1, 아니면 0을 리터한다.
재귀로 돌며 리턴된 1,0을 통해 cnt를 계산하여 리턴한다.

전체 코드

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

public class Solution 
{
    public static int solution(int[] numbers, int target) 
    {
        return DFS(numbers,0,target,0);
    }
    public static int DFS(int[] array, int index,int target,int sum)
    {
        int cnt=0;
        if(index == array.Length)
        {
            if(sum == target)
            {
                return 1;
            }
            return 0;
        }
        cnt =cnt + DFS(array,index+1,target,sum+array[index]);
        cnt =cnt + DFS(array,index+1,target,sum-array[index]);
        return cnt;
    }
    public static void Main(string[] args)
    {
        int[] numbers = new int[] {1,1,1,1,1};
        int target = 3;
        Console.WriteLine(solution(numbers,target));
    }
}