💻 타켓 넘버

❓ 문제

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

✔️ 코드

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

    // 문제상 numbers 각각의 원소들이 + - 인 경우로 총 2의 numbers.length 제곱 만큼의 경우의 수발생
    // 하나의 원소당 2가지의 경우의 수가 발생하므로 나뭇가지식으로 재귀를 돌린다.

    const getSum = (index, sum) => {
        // index는 numbers의 원소 인덱스
        // sum은 첫번째 원소 +- 두번쨰 원소 .. 등등 계속 더하거나 빼며 결과를 이어나간다.
        if (index < numbers.length) {
            getSum(index + 1, sum + numbers[index]);
            getSum(index + 1, sum - numbers[index]);
            // 모두 원소를 더하거나 뻇을떄 결과값이 target과 같다면 답 추가
        } else {
            if (sum === target) {
                answer++;
            }
        }
    }
    //재귀의 인덱스는 처음부터 시작하며 시작값은 0이다.
    getSum(0, 0);
    return answer;
}

let numbers = [1, 1, 1, 1, 1];
let target = 3;
console.log(solution(numbers, target));

❗️풀이과정

n개의 수를 더하고 빼면서 target을 만들어야 하는데 이 방법의 수가 다르려면 n개의 수 각각 양수 혹은 음수여하한다. 즉, 총 경우의 수는 2의 n제곱과 같다. 이러한 경우를 모두 훑어야하는데 단순 for문을 돌리기에는 반복문의 생성조건이 까다롭다. 따라서 재귀함수로 접근한다.

n개의 수가 길이가 n인 배열(numbers)에 담겨있다고 한다면 각 숫자가 담겨 있는 칸의 순번을 index라고 하자

index가 1이라면 numbers[1] 은 -인 경우와 +인 경우로 나눌수 있다.
그렇다면 일단 여기까지 모두 더한 결과는 sum에 저장하자

index가 2이라면 numbers[2]는 numbers[1]이 양수 혹은 음수인 경우에 따라 또 양수 혹으 음수로 갈라진다. 따라서 2의 n제곱 만큼의 결과가 나온다.

이것을 재귀함수로 표현한다면 위와 같다.

📄 배운점

• 재귀함수로서 dfs 비슷하게 모든 경우의 수를 훑는 방법을 견식하고 배웠다.