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

난이도: Level 2

 

사용 알고리즘: DFS

 

index를 돌면서 모든 경우의 수들 중 sum이 target과 일치하면 되는 문제였다.

그림(못남)처럼 dfs로 모든 경우의 수를 따라가도록 하였다.

 

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    
    var count = 0
    
    func dfs(idx: Int, sum: Int) {
        if idx == numbers.count && sum == target {
            count += 1
            return
        }
        
        if idx + 1 <= numbers.count {
            dfs(idx: idx + 1, sum: sum + numbers[idx])
            dfs(idx: idx + 1, sum: sum - numbers[idx])
        }
    }
    
    dfs(idx: 0, sum: 0)
    
    return count
}