> For the complete documentation index, see [llms.txt](https://songeun.gitbook.io/coding-test/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://songeun.gitbook.io/coding-test/kit/dfs-bfs/1.md). # 타겟 넘버 ## **문제 설명** 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 이하인 자연수입니다. **입출력 예** | numbers | target | return | | ---------------- | ------ | ------ | | \[1, 1, 1, 1, 1] | 3 | 5 | | \[4, 1, 2, 1] | 4 | 2 | **입출력 예 설명** **입출력 예 #1** 문제 예시와 같습니다. **입출력 예 #2** ``` +4+1-2+1 = 4 +4-1+2-1 = 4 ``` * 총 2가지 방법이 있으므로, 2를 return 합니다. ## 코드 스스로 해결하지 못하고 찾아본 풀이 코드이다. [참고](https://yong-nyong.tistory.com/41) ```javascript function solution(numbers, target) { let answer = 0; const length = numbers.length; function dfs(count, sum) { if (count === length) { if (target === sum) { answer++; } return; } dfs(count + 1, sum + numbers[count]); // 재귀함수(1) dfs(count + 1, sum - numbers[count]); // 재귀함수(2) } dfs(0, 0); return answer; } ``` #### 코드 풀이 문제에서 + - 의 조합을 통해 `target`의 값을 가지는 경우의 수를 구해야 했다. 그래서 **DFS 탐색**을 통해 모든 + - 를 조합하는 **경우의 수**를 구한 뒤, 해당 조합과 `numbers` 배열에 매치시켜 연산했을 때`target`에 해당하는 값과 일치하는 개수를 찾는 방식이다. `dfs(count, sum)` 함수에서 `count`로 **중단될 지점**을 지정해주고, 숫자들의 합을 넘겨줄 `sum` 인수 두 가지를 지정하였다. **재귀 종료 조건** `count` 가 배열의 길이랑 같아지고, `target` 과 `sum` 의 값이 같다면 `answer` 의 값을 증가시키고 함수를 종료시키도록 되어있다. **재귀 실행 과정** dfs 함수에 count 를 +\` 증가시키고, 연산자 '+'를 계산할 수 있도록 sum과 numbers의 숫자 하나를 꺼내 합을 계산한 값을 인수로 주고, '+'를 계산한 함수가 끝났다면 연산자 '-'를 계산할 수 있도록 sum과 numbers의 숫자 하나를 꺼내서 차이를 계산한 값을 인수로 주었다.
```javascript numbers = [4, 1, 2, 1], target = 4; dfs(0,0); dfs(count + 1, sum + numbers[count]); // 재귀함수(1) count = 0, sum = 0 → df(1, numbers[0]); // '+' 연산자 // dfs(1, 4); count = 1; sum = 4; → dfs(2, 4+numbers[1]); dfs(2, 5); count = 2; sum = 5; → dfs(3, 5+numbers[2]); dfs(3, 7); count = 3; sum = 7; → dfs(4, 7+numbers[3]); dfs(4, 8); count = 4; sum = 8; → 종료조건 count = numbers.length // 4+1+2+1 = 8 // 종료조건을 만나 재귀를 종료하고, target == sum 조건에 맞는다면 answer++ // 재귀함수(1)을 종료하고 종료되는 재귀를 부르는 시점으로 돌아가서 다음 코드를 실행한다. // count = 3, sum = 7; dfs(count+1, sum-numbers[count]); // 재귀함수(2) '-' 연산자 dfs(4, 6); count = 4; sum = 6; → 종료조건 count = numbers.length // 4+1+2-1 = 6 // 재귀 종료, 재귀를 부르는 시점으로 돌아가서 다음 코드 없으므로 다시 재귀함수(1) 실행 // count = 2; sum = 5; dfs(3, 3); count = 3; sum = 3; → dfs(4, 3+numbers[3]); dfs(4, 4); count = 4; sum = 4; → 종료 // 4+1-2+1 = 4 // 종교 재귀 다음 코드 실행 // count = 3; sum = 3; dfs(count+1, sum-numbers[count]); // 재귀함수(2) '-' 연산자 dfs(4, 2); → 종료 // 4+1-2-1 = 2 ... ``` > 아직까지 직접 재귀함수를 짜는 것은 어려운 것 같다. 좀 더 많은 연습이 필요한 것 같다.