프로그래머스 - 타겟 넘버 (JavaScript)

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

프로그래머스

문제 해결 과정

모든 원소를 사용해야하는데

숫자는 더하거나 빼는 2가지 경우의 수가 있다.

모든 원소를 더하거나 빼보는 모든 경우의 수를 탐색하지 않고

타겟넘버를 구할 수 있는 방법은 생각이 나지 않아서

깊이우선탐색으로 모든 케이스를 탐색하기로 했다.

1. 현재 몇 개까지 계산했는지 확인하는 count랑 계산된 값 sum을 매개변수로 하는 재귀함수를 작성
2. 더하거나 빼는 경우의 수를 확인하기 위해 재귀를 +,- 각각 실행한다.
3. 탈출조건 => 모든 원소를 사용했다.
4. 탈출 전에 계산된 값이 타겟넘버와 같으면 answer++

코드

function solution(numbers, target) {
    var answer = 0;
    
    function recursion(count, sum){
        if(count===numbers.length){
            if(sum===target){
                answer++
            }
            return
        }
        recursion(count+1, sum+numbers[count])
        recursion(count+1, sum-numbers[count])
    }

    recursion(0,0)
    
    return answer;
}

 

생각해보고 싶은 점

.

---

출처:

프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges