[Javascript] 프로그래머스 - 타겟 넘버

🧾 목차

1. 문제 설명

2. 문제 풀이

3. 정답 코드

---

1. 문제 설명

n개의 음이 아닌 정수가 있을 경우,

1) 이 정수들의 순서를 변경하지 않고 2) 빼거나 더해서 만들 수 있는 수 중에서 타겟 넘버가 될 경우 카운트해라

 

입출력

 

제한 사항

2 <= number.length <= 20

 

2개의 연산자(+, -)를 사용하여 모든 경우의 수를 구한다면 시간 복잡도는 2^20 ≈ 1,000,000

👉 모든 경우의 수를 구해도 됨!

---

2. 문제 풀이

2개의 연산자(+, -)를 사용하여 모든 경우의 수를 구해야 하는 문제 => dfs 재귀함수를 구현

<< 종료 조건 >>
1. 모든 숫자를 모두 사용 + 타겟 넘버가 완성된 경우 
  👉 answer + 1, 종료
2. 모든 숫자를 모두 사용 + 미완성
  👉 종료

 

---

3. 정답 코드

function solution(numbers, target) {
    var answer = 0;
    comb(0, 0);
    
    function comb(curNum, curIdx) {
        // 종료 조건: 모든 숫자를 모두 사용했을 경우
        if (curIdx == numbers.length) { 
            // 타켓 넘버를 만들 수 있는 경우
            if (curNum == target)  {
                answer++;
            }
            
            return; // 더 이상의 연산을 진행하지 않음
        }
        
        // 2가지의 연산(덧셈, 뺄셈) 중 택 1
        comb(curNum + numbers[curIdx], curIdx + 1); 
        comb(curNum - numbers[curIdx], curIdx + 1);
        
    }
    
    
    return answer;
}

---