# 타겟 넘버
## **문제 설명**
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
...
```
> 아직까지 직접 재귀함수를 짜는 것은 어려운 것 같다. 좀 더 많은 연습이 필요한 것 같다.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://songeun.gitbook.io/coding-test/kit/dfs-bfs/1.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.