[Swift] 프로그래머스 - 타겟 넘버

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

코딩테스트 연습 - 타겟 넘버

 

 

 

numbers = [1, 2, 3, 4, 5] 라고 할 때, (1에 +, -를 붙인 경우) * (2에 +, -를 붙인 경우) * .... (마지막 숫자까지 +, -를 붙인 경우)를 곱하면 모든 경우가 나옵니다. 마지막 숫자까지 붙였을 때에 target과 똑같다면 결괏값에 +1을 해주면 됩니다.

 

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var result = 0
    
    // 인덱스, 값
    func dfs(i: Int, current: Int) {
        if i == numbers.count { // 모든 숫자를 사용하면
            if current == target { // 현재 값이 target과 같으면
                result += 1
            }
            return
        } else {
            dfs(i: i + 1, current: current + numbers[i])
            dfs(i: i + 1, current: current - numbers[i])
        }
    }
    
    dfs(i: 0, current: 0)
    
    return result
}

solution([1, 1, 1, 1, 1], 3) // 5
solution([4, 1, 2, 1], 4) // 2