프로그래머스 JS [타겟 넘버]⭐⭐ 재귀, DFS

• 타겟 넘버

문제 설명

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 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

---

지~옥의 재귀함수 이해 재귀함수는 종료 조건을 정하고, 할 일을 지정해주면 결과를 알아서 출력해주는 선언적 프로그래밍 방식이다. https://www.youtube.com/watch?v=uSSC0aKXbWQ&t=650s     종료조건: 깊이가 5일 때 종료해 줘.     if (depth === numbers.length) {         return     }     근데 종료하기 전에 하나만 부탁하자.      sum과 target이 같다면 answer++ 해줘.     if (sum === target) {         answer++;     }       할일은 이거야.     numbers의 각 인덱스마다 +, -를 시행해 줘.     depthFirstSearch(depth + 1, sum + numbers[depth])     depthFirstSearch(depth + 1, sum - numbers[depth]) 이렇게 시키면 메모리에서 일어나는 일 (내가 이해한) 처음은 (0, 0) 이므로 depth00 으로 표현 해봅시다. depth00은 depth11과 depth1-1 을 데려옵니다. [1] [-1] depth11은 depth22와 depth20을 데려옵니다. [1,1] [1,-1] depth1-1은 depth20과 depth2-2를 데려옵니다. [-1,1] [-1,-1] depth22는 depth33과 depth31을 데려옵니다. [1,1,1] [1,1,-1] depth20은 depth31과 depth3-1을 데려옵니다. [1,-1,1] [1,-1,-1] depth22는 depth33과 depth31을 데려옵니다. [-1,1,1] [-1,1,-1] depth2-1은 depth31과 depth3-3을 데려옵니다. [-1,-1,1] [-1,-1,-1] 이렇게 1과 -1을 depth땡땡 마다 추가해줍니다. 종료조건(깊이5)에 도달할때까지 진행합니다. depth11 > depth22 > depth 33> depth44 > depth55 그럼 2^5 개의 depth땡땡 들이 depth5땡 이 되어 종료조건에 도달해 스택 안에 쌓이게 됩니다. 스택 = [ 2^5 개의 dehtp땡땡 배열 ] 이제 depth00 > depth11 > depth22 > depth 33> depth44 > depth55  를 거친 녀석은 [1,1,1,1,1] 배열을 가지고, 종료조건을 실행합니다.  sum === target이 아니므로 그냥 종료하고 스택에서 제외됩니다. 나머지 31개의 depth땡땡 들도 마찬가지로 종료조건을 실행하게 되고 [-1,1,1,1,1] 같이 sum === target이면 answer++ 를 하고 종료합니다.

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