programmers - 깊이 우선 탐색- 타겟 넘버

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

∙ 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
∙ 각 숫자는 1 이상 50 이하인 자연수입니다.
∙ 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

---

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

접근방식
1) numbers의 각 요소가 +,-가 되는 경우로 분리해서 생각
2) 순환 호출(재귀 함수)로 +,- 케이스를 분류
3) recur 함수의 재귀를 통해 k라는 숫자를 0부터 numbers.length 까지 진행

마지막으로 +,- 가 번갈아 계산되고, 첫 요소의 +,- 분류를 위해서 recur 함수를 2번씩 순환하고 index가 되는 numbers.length가 되는 순간
누적한 sum이 target과 일치할 때 answer를 하나씩 올려서 카운팅하고 반환

+) python version

def solution(numbers, target):
    answer = dfs(numbers, 0, 0, target)
    return answer

def dfs(nums, index, summary, tar):
    ret = 0
    if index == len(nums):
        if summary == tar:
            return 1
        else:
            return 0
        
    ret += dfs(nums, index + 1, summary + nums[index], tar)
    ret += dfs(nums, index + 1, summary - nums[index], tar)
    
    return ret