타겟 넘버

문제

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 이하인 자연수입니다.

---

풀이방법

function solution(numbers, target) {
    let answer = 0; // 가능한 경우의 수를 저장할 변수

    // 재귀 함수 정의
    function getAnswer(x, value) {
        if (x < numbers.length) { // x가 numbers.length보다 작은 동안에 실행된다.
            // 현재 인덱스의 원소를 더하거나 빼는 두 가지 경우의 수로 재귀 호출
            getAnswer(x + 1, value + numbers[x]); // 더하는 경우
            getAnswer(x + 1, value - numbers[x]); // 빼는 경우
        } else { // 모든 원소를 사용한 경우
            if (value === target) { // 타겟 값과 일치하는 경우
                answer++; // 가능한 경우의 수 증가
            }
        }
    }

    getAnswer(0, 0); // 재귀 함수 호출 시작

    return answer; // 가능한 경우의 수 반환
}

 

이 코드는 주어진 숫자 배열 numbers와 목표 숫자 target이 주어졌을 때, 주어진 숫자들을 더하거나 빼서 target 숫자를 만들 수 있는 경우의 수를 계산하는 재귀 함수입니다. 코드를 구성하는 주요 부분을 설명하겠습니다.

1. getAnswer 함수: 이 함수는 재귀적으로 호출되며, 두 개의 매개변수 x와 value를 받습니다. x는 현재 처리 중인 숫자의 인덱스를 나타내고, value는 현재까지의 더하거나 빼서 얻은 값입니다.
2. if (x < numbers.length): 현재 처리 중인 숫자 인덱스 x가 배열 numbers의 길이보다 작은 동안에는 실행됩니다.
3. getAnswer(x + 1, value + numbers[x]); 및 getAnswer(x + 1, value - numbers[x]);: 현재 숫자를 더하는 경우와 빼는 경우 두 가지로 재귀적으로 함수를 호출합니다. 이렇게 하면 모든 가능한 조합을 탐색하게 됩니다.
4. else: 모든 숫자를 사용한 경우입니다. 모든 숫자를 사용한 후에 value와 target을 비교하여 같으면 answer를 증가시킵니다. 이것은 주어진 숫자들을 더하거나 빼서 target 숫자를 만들 수 있는 경우의 수를 계산하는 부분입니다.
5. getAnswer(0, 0);: getAnswer 함수를 초기에 호출하고, 인덱스 0부터 시작하고 현재 값은 0으로 시작합니다.

첫 번째 호출에서 x가 0이므로 x는 배열의 첫 번째 숫자를 가리킵니다. 그런 다음 재귀 호출을 통해 다음 인덱스로 넘어가고, 두 가지 경우(더하거나 빼는 경우)를 처리합니다. 이런 식으로 재귀 호출이 이루어지며, 모든 숫자의 인덱스를 처리하게 됩니다.

기본적으로 getAnswer 함수는 각 숫자를 사용하거나 사용하지 않는 두 가지 상황을 모두 고려하며, 이를 통해 가능한 모든 숫자 조합을 탐색합니다. 그래서 x가 0에서 시작하는 것이 맞고, 이를 통해 첫 번째 숫자부터 시작하여 모든 숫자를 처리할 수 있습니다.

이러한 재귀적인 접근을 통해 모든 가능한 경우의 수를 검사하고, 그 중에서 target 숫자를 만족하는 경우의 수를 세어 answer로 반환합니다