프로그래머스 타겟넘버

class Solution {
    var answer = 0
    
    fun solution(numbers: IntArray, target: Int): Int {
        dfs(numbers, target, 0)
        return answer
    }
    
    fun dfs(numbers: IntArray, target: Int, depth: Int) {
        if (depth == numbers.size) {
            var sum = 0
            for (i in numbers.indices) {
                sum += numbers[i]
            }
            if (sum == target) {
                answer++
            }
            return
        } else {
            dfs(numbers, target, depth + 1)
            numbers[depth] *= -1
            dfs(numbers, target, depth + 1)
        }
    }
}

/*

depth가 numbers.size가 되기전에 target 값과 같은 경우를 생각할 수 있는데.. 뒤에 계산까지 고려하여 완전 탐색으로 모든 경우를 계산

*/

 

문제 풀이의 핵심은 해당 depth의 넘버가 +일 경우와 -일 경우의 완전 탐색이다.