[Algorithm] 프로그래머스 타켓넘버

문제 설명

나의 풀이

import Foundation
func solution(_ numbers:[Int], _ target:Int) -> Int {
    var count = 0
    
    func dfs(index: Int, sum: Int) {
        if index == (numbers.count - 1) && sum == target {
            count += 1
            return
        }
        guard index + 1 < numbers.count 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 count
}

고민한 점

트리의 각 레벨을 numbers의 index라고 생각하고 문제를 해결하면된다. 그리고 dfs로 다음 index을 더하거나 뺀 뒤, 인덱스의 마지막까지 갔을 때 target과 일치하는지 확인해보면 된다.

참고

Programmers
momo_9 타겟넘버