타겟 넘버 javascript - 프로그래머스

문제이해

주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
그리고 저는 모든 숫자에 + , - 부호를 붙여서 누적할 것입니다. 그 누적 값이 타겟 넘버와 같으면 answer를 1씩 증가해줄 겁니다.

로직

최대 20개의 숫자를 늘어놓고, 각 숫자를 뽑아서 + 부호를 붙여서 누적할지, -부호를 붙여서 누적할지
이 두가지 경우가 존재합니다. 즉 2^20가지수가 존재합니다.

백만이 조금 넘어가는 수입니다. <<< 1억
1억에 비해서는 충분히 작은 수입니다. 보통 1초에 1억번 연산한다고 가정을 하고 시간복잡도를 계산합니다.
이건 알고리즘 문제해결전략에서 읽은내용입니다.

코드는 위에 말한 로직을 그대로 구현합니다.

code

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