Level2 - 타겟 넘버

타겟 넘버

문제 설명

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 함수를 작성해주세요.

---

코드

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var result = 0

    func dfs(index: Int, sum: Int) {
        if sum == target && index == numbers.count - 1 {
            result += 1
            return
        }
        guard index < numbers.count - 1 else {return}

        dfs(index: index + 1, sum: sum + numbers[index + 1])
        dfs(index: index + 1, sum: sum - numbers[index + 1])
    }

    dfs(index: -1, sum: 0)
    return result
}

---

깊이/너비 우선탐색 (DFS/BFS) 문제이다.
이 문제의 경우 dfs를 재귀함수를 이용하여 구현했다.
루트노드를 0으로 두고 numbers 배열을 하나씩 더해주거나 빼주는 재귀함수를 만들었다.

index와 numbers의 크기가 같은지를 판별해 단말노드까지 탐색했는지를 확인하였고
sum과 target의 값이 같은지를 판별해
결과값의 카운트를 늘려주었다.