[swift] 타겟넘버

📌 프로그래머스 Lv - 2

...

📝 KeyWord

⇢ DFS
⇢ 점화식 [ "Sn = Sn-1 + k" || "Sn = Sn-1 - k" ]

📌 문제풀이

---

⇢ 순서 변경없이, 해당 숫자들의 부호를 어떻게 변경할지
⇢ target에 도달하기위해 모든 숫자가 사용되었는지 확인.

(1) 문제 조건 확인, "모든 숫자를 사용하여, 부호를 변경하며 target에 도달"
(2) DFS를 통해, depth를 하나씩 증가하며, 배열의 개수와 같고 합이
      target과 동일하다면 answer += 1

해당 문제를 풀면서 조건에 따라 "모든 숫자를 활용해야한다"는 사실을 알면서도
단순히, "target 과 sum이 동일하다면" 이라는 조건을 통해 DFS를 구현하다보니 계속 오답이 출력되었다..

📝 전체코드

---

import Foundation

func dfs(_ target: Int, _ numbers:[Int], _ depth: Int, _ sum: Int , _ answer: inout Int){
    if depth == numbers.count && target == sum { 
        answer += 1 
        return 
    } else if depth < numbers.count
    {
        dfs(target, numbers, depth + 1 , sum + numbers[depth], &answer)
        dfs(target, numbers, depth + 1 , sum - numbers[depth], &answer)
    }
}


func solution(_ numbers:[Int], _ target:Int) -> Int {
    
    var answer = 0
    dfs(target, numbers,0, 0, &answer)
    return answer
}