프로그래머스 #5

DFS/BFS - 타겟 넘버

function solution(numbers, target) {
    const queue = [];
    const enqueue = (el) => queue.push(el);
    const dequeue = () => queue.shift();
    const N = numbers.length;
    let count = 0;
    
    enqueue([[numbers[0]], numbers[0], 1]);
    enqueue([[-numbers[0]], -numbers[0], 1]);
    
    while(queue.length > 0){
        const [arr, sum, idx] = dequeue();
        
        if(arr.length < N){
            enqueue([[...arr, numbers[idx]], sum+numbers[idx], idx+1]);
            enqueue([[...arr, -numbers[idx]], sum-numbers[idx], idx+1]);
        } else {
            if(sum === target){
                count++;
            }
        }
    }
    
    return count;
}

흠...O(2^N)의 효율적이지 못한 로직인듯!

210715
너무 어렵게 생각했나보다 ㅎ

function solution(numbers, target) {
    let count = 0;
    
    const aux = (num, idx) => {
        if(idx === numbers.length){
            if(num === target) count++
            return;
        }
        
        aux(num+numbers[idx], idx+1);
        aux(num-numbers[idx], idx+1);
    }
    
    aux(numbers[0], 1);
    aux(-numbers[0], 1);
    
    return count;
}

단순한 DFS문제 였음