[프로그래머스] DFS _ 타켓 넘버

2021_11_21 알고리즘 스터디 문제 풀이

문제 URL 

코딩테스트 연습 - 타겟 넘버

 

문제

 

수도코드

dfs 재귀함수를 만든다. 인덱스와 sum을 인자로 받음
    탈출 조건
          인덱스가 numbers.length와 같은 경우 
          sum과 target이 같아진 경우 경우의 수를 1 증가시킨다 
    양수 조건으로 인덱스 1씩 증가시키며 재귀함수 호출
    음수 조건으로 인덱스 1씩 증가시키며 재귀함수 호출

최종 result 리턴한다

 

풀이

function solution(numbers, target) {
    let result = 0;
    dfs(0, 0);
    function dfs(idx, sum) {
        if(idx === numbers.length) {
            if (sum === target) {
                result++;
             }
            return;
        }
        dfs(idx + 1, sum + numbers[idx]);
        dfs(idx + 1, sum - numbers[idx]);
    }
    return result;
}