[DFS] 프로그래머스 '타겟 넘버' - js

1. 문제

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

프로그래머스

2. 코드

DFS의 기본은 재귀(피보나치 수열 생각하기)다! 문자열을 계속 이어붙히거나, 순서들을 나열할 때는 for문을 사용하지만, 이 문제처럼 단순히 총 합을 target과 비교하는 것이면 for문을 사용할 필요가 없다. 기본 재귀 개념 사용하자!

무조건 for문을 써야한다는 틀에 박혀 한시간을 헤맸다...

그리고 또 하나 중요한 것! 엣지케이스를 정확하게 작성하자. 

재귀에서 스택 오버플로우가 난다? === 무한루프!? ->엣지케이스를 확인하자!

dfs 파라미터

• idx : numbers에 있는 모든 숫자를 사용하여 연산해야 하기 때문
• sum : 모든 숫자를 사용한 연산을 마치고 target과 같은지 확인해야 하기 때문

// 1+1+1+1+1
// 1+1+1+1-1
// 1+1+1-1+1
// 1+1+1-1-1
...

function solution(numbers, target) {
    let ans = 0;

    const dfs = (idx,sum) => {
       if(idx === numbers.length){
           if(sum === target) ans++;
           return;
       }
        dfs(idx+1,sum+numbers[idx]);
        dfs(idx+1,sum-numbers[idx]);
    }
    
    dfs(0,0);
    
    return ans;
}

 

복기

3/29
4/14