타겟 넘버

🔒 문제

🧠 생각의 흐름

사실 문제 분류에서 이미 DFS/BFS 라고 명시해 놨기 때문에
모든 경우의 수를 구하는 Backtracking 알고리즘을 떠올릴 수 밖에 없었다.
다음과 같이 생각했다.

(1) 모든 숫자를 나열한다.

N개 숫자라면 N! / 중복숫자! 일 것이다.

(2) 나열한 숫자에 대해 + , - 를 붙여준다.

이는 각 자리수에 2개의 경우의 수이므로 N개 숫자라면
2^N 가지 가 나온다.

∴ 모든 경우의수 == (1) + (2) == (N! / 중복된 숫자개수!) * 2^N

시간복잡도가 높으므로 백트래킹의 핵심인 '가지치기 (pruning)'를 할만한 방법이 없을 까 고민했는데
numbers를 오름차순정렬하거나 BST에 담아 노드까지의 총합과 나머지 노드의 합을 조사하여 답까지 도달 가능여부를 비교해 보는 방법이 있었다.
하지만 이마저도 + - 두 가지 경우 모두 따져야 하므로 소요 시간에 별 차이가 없어보여 그냥 brute force로 모든 경우의 수를 구했다.

🔑 풀이

class Solution {
    var totalSum : Int = 0
    var targetNumber : Int = -1
    var answer = 0
    lateinit var nodes : IntArray

    private fun  dfs (index: Int) {
        totalSum += nodes[index]
        if (index == nodes.size - 1) {
            if (totalSum == targetNumber) answer++
        } else {
            dfs(index + 1)
        }

        // 음수 조사
        totalSum -= nodes[index] * 2
        if (index == nodes.size - 1) {
            if (totalSum == targetNumber) answer++
        } else {
            dfs (index + 1)
        }

        // redo and go up to previous node
        totalSum += nodes[index]
    }

    fun solution(numbers: IntArray, target: Int): Int {
    
        // (1) 양수 배열 numbers 를 기본 케이스로 둔다.
        // (2) Backtracking using DFS
        // (3) 해당 노드 (숫자)를 양수, 음수버전으로 2개 노드로 나누어 분기한다.
        // (4) 맨 마지막 depth (총합이 다 구해진 상태) totalSum과 target을 비교한다.
        // 주어진 numbers 배열 자체가 adjacencyList 와 다를게 없는 문제므로 visited Boolean 배열은 필요하지 않다..


        //member field initialize
        nodes = numbers
        targetNumber = target

        dfs(0)
        return answer
    }

}