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

문제 풀이 아이디어

완전탐색을 통해서 모든 경우의 수를 찾아야 합니다. dfs로 구현할 수 있습니다. 다만 주의할 점은 dfs를 할 때 기계적으로 반복문을 사용하려는 경향이 있습니다. (저만 그런가요;;;)

하지만 이 문제의 경우 숫자의 순서를 그대로 유지해야 합니다. 따라서 반복문 없이 그냥 다음 index만 dfs를 실행하면 됩니다.

코드

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var cnt = 0
    var result = 0
    
    func dfs(_ index: Int) {
        // 탈출 조건
        if index == numbers.count {
            if result == target { cnt += 1 }
            return
        }
        
        // 순서를 유지해야 하므로 현재 index만 탐색을 실행한다.
        result += numbers[index]
        dfs(index + 1)
        result -= numbers[index]
        
        result -= numbers[index]
        dfs(index + 1)
        result += numbers[index]
    }
    
    dfs(0)

    return cnt
}