[C#] 프로그래머스 LV.2 타겟 넘버 (DFS)

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

DFS문제이다. 재귀를 통해 모든 경우의 수를 탐색해야 하기 때문에 DFS를 통해 문제를 해결하였다.

 

using System;

public class Solution
{
    public int MaxCount = 0;

    public int solution(int[] numbers, int target)
    {
        return DFS(numbers, target, 0, 0);
    }

    private int DFS(int[] numbers, int target, int index, int sum)
    {
        if(index == numbers.Length)
        {
            return sum == target ? 1 : 0;
        }

        int add = DFS(numbers, target, index + 1, sum + numbers[index]);
        int subtract = DFS(numbers, target, index + 1, sum - numbers[index]);

        return add + subtract;
    }

    public static void Main(string[] args)
    {

        Solution s = new Solution();

        int target = 3;

        int[] numbers  = { 1, 1, 1, 1, 1 };

        int result = s.solution(numbers, target);

        Console.WriteLine(result);
    }
}

 

index(numbers 배열의 크기) 0 과 sum(총합) 0 을 초기값으로 두고, sum이 target 수와 같을 경우 1을 반환하는 식으로 하여 모든 경우의 수를 탐색한다.

 

index 5, sum 5까지 탐색한 후 재귀를 통해 다시 4, 2 5, 3 ... 이런식으로 돌아가서 모든 경우의 수를 반환시킨다.