[알고리즘] DFS 문제 - 더하기 빼기

스스로가 생각했을 때 아직 DFS BFS관련 문제 해결능력이 부족하다고 생각했고, 관련 문제를 풀던중 문제가 직관적이진 않지만 재미있는 DFS의 활용 문제라고 생각해서 가져와 봤다.

 

 

---

 

해당 문제 에서는 각 경로를 끝까지 따라갔을 때의 총합이 target 값 과 동일하게 나오는 방법의 수를 원하였고 이때 index의 각 숫자들은 같은 수가 + 와 - 의 2가지 경우의 수로 매번 나뉘기 때문에 해당 + 와 - 로 갈리는 구간을 재귀함수로 나타내면 좋겠다고 생각하였다.

그리고 target 값에 만족하는 경우를 1로 리턴하도록 하여 모든 경우의 수의 DFS값이 최종적으로 원하는 return값이 되도록 아래와 같이 코드를 만들었다.

 

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

        // 현재 숫자를 더하는 경우와 빼는 경우를 모두 탐색
        return DFS(numbers, target, index + 1, sum + numbers[index]) +
               DFS(numbers, target, index + 1, sum - numbers[index]);
    }