[프로그래머스] 타겟넘버 (Swift) ※1,2번 실행초과

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

프로그래머스

DFS 깊이 우선 탐색 알고리즘으로 푼 코드

- 탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식

 

import Foundation

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

 

※1,2번 실행초과

재귀 함수와 Array, Dictionary를 통한 코드

- 필요없는 반복문으로 실행초과 발생

 import Foundation

 func solution(_ numbers:[Int], _ target:Int) -> Int {
     var result = 0
     var allcase: [[Int]:Bool] = [:]
     var numArray = [Int]()
     
     func visit(_ indexArray: [Int]){
         
             numArray = numbers
             for i in indexArray{
                 numArray[i] *= -1
             }
             if numArray.reduce(0,+) == target{
                 allcase[indexArray] = true
                 result += 1
             }else{
                 allcase[indexArray] = false
             }
         
         for i in 0..<numbers.count{
             if !indexArray.contains(i){
                 let sortedArray = (indexArray + [i]).sorted(by:<)
                 if allcase[sortedArray] == nil{
                     visit(sortedArray)
                 }
             }
         }
     }
     
     for i in 0..<numbers.count{
         visit([i])
     }
     
     
     return result
 }