문제

input
numbers = [4, 1, 2, 1]
target = 4

process

+4+1-2+1 = 4
+4-1+2-1 = 4

output
2

문제 풀이

numbers의 각 요소를 그래프의 노드로 치환한다. 이때 모든 요소는 +-값을 가질 수 있으므로 아래와 같은 그래프를 생각할 수 있다.

DFS

담부턴 아이패드 써야겠다.

방문한 노드에서, 각각의 자식 노드에 대한 DFS를 재귀적으로 호출한다.

solution function signature

void DFS(Number idx, Number sum)

• idx: 별도의 그래프를 구성하지 않고, numbers 배열의 포인터로 사용한다. 배열의 크기를 벗어났을 때를 재귀 호출 종료 조건으로 사용할 수도 있다.
• sum: 호출된 시점에서의 합을 보관한다. 재귀 호출 종료 전, target 값과 일치하면 방식을 하나 찾은 것이므로 answer에 1을 더한다.

code

function solution(numbers, target) {
    let answer = 0;
    
    const DFS = (idx, sum) => {
        if (++idx === numbers.length) {
            if (sum === target) {
                answer += 1;
            }
            return;
        }
        const currentNode = numbers[idx];
        DFS(idx, sum + currentNode)
        DFS(idx, sum - currentNode)
    }
    
    DFS(-1, 0)
    
      return answer;
}