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

코드

function dfs(numbers, idx, now, target) {
    let ret = 0;
    if(idx === numbers.length)
    {
        return now === target ? 1 : 0        
    }
    else {
        
        ret += dfs(numbers, idx+1, now + numbers[idx], target)
        ret += dfs(numbers, idx+1, now - numbers[idx], target)
    }
        
    return ret;
}

function solution(numbers, target) {
    var answer = 0;
    var sum = [numbers[0], -numbers[0]];
    for(let i=1;i<numbers.length;i++) {
        let newSum = [];
        for(let j=0;j<sum.length;j++) {
            newSum.push(sum[j] + numbers[i])
            newSum.push(sum[j] - numbers[i])
        }
        sum = newSum;
    }
    
    for(let i=0;i<sum.length;i++) {
        if(sum[i] === target) answer++;
    }
    
    // return dfs(numbers, 0, 0, target);
    
    return answer;
}

풀이 및 소감

두가지 방법으로 문제를 해결했다.
첫번째는 for문을 활용하여 새로운 sum 배열에 값들을 늘려가면서 해결했다.
두번째는 재귀를 활용하여 문제를 해결했다.