[Programmers] 타겟 넘버

문제

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

n개의 음이 아닌 정수가 있습니다.

이 수를 적절히 더하거나 빼서
타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면
다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers,
타겟 넘버 target 이 매개변수로 주어질 때

숫자를 적절히 더하고 빼서
타겟 넘버를 만드는 방법의 수를 return 하도록
solution 함수를 작성해주세요.

---

필요한 사전 지식

DFS

깊이 우선 탐색

재귀함수

재귀함수를 이해하기 위해 스택의 개념을 복습했다.
재귀함수로 DFS 를 구현할 수 있다.

---

나의 풀이

function solution(numbers, target) {
    let answer = 0;

    function recur(arr) {
        if (arr.length === numbers.length) { // 탈출 조건
            if (arr.reduce((ac, cu) => ac + cu) === target) {
                answer++
            }
            return
        }
        arr.push(numbers[arr.length]);
        let a = [...arr];

        arr.pop();
        arr.push(-numbers[arr.length]);
        let b = [...arr];

        recur(a);
        recur(b);

    };

    recur([]);

    return answer;
}

재귀의 과정 :

1. 탈출조건으로 함수가 리턴될 때까지
   recur(a)까지 실행되며
   스택으로 쌓인다.

2. 스택은 나중에 들어온 것을 먼저 처리한다.
   각 스택은 코드 순서상
   recur(a) 밑에 실행되는
   recur(b)를 아직 수행하지 않은 상태로
   recur(b)를 마저 수행해서 처리된다.

3. recur(b) 에서도 recur(a)가 다시 실행될 수 있으며
   recur(a) 실행시 1, 2번을 반복한다.