[프로그래머스/Lv.2] 타겟 넘버

<문제>

 

 

<접근 방식>

1) DFS함수를 numbers 크기만큼 재귀한다. 이때 총 합이 target과 동일하면 answer을 카운팅 후 numbers 크기만큼 재귀했다면 재귀를 종료한다.

2) DFS를 호출 할 때 마다 index값을 올려준다. '-' or '+' 연산을 수행한다. (반복)

 

 

<코드>

class Solution {
    
    int arr[];
    int targetNum, answer;
    int arrLength;
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        targetNum = target;
        arrLength = numbers.length;
        arr = new int[arrLength];
        
        for(int i = 0; i < arrLength; ++i) {
            arr[i] = numbers[i];
        }
        
        dfs(1, -1 * arr[0]);
        dfs(1, arr[0]);
        
        return answer;
    }
    
    private void dfs(int index, int sum){
        if(index == arrLength && sum == targetNum){
            answer++;
            return;
        }
        
        if(index >= arrLength) return;
        
        
        dfs(index + 1, sum + arr[index]);
        dfs(index + 1, sum - arr[index]);
    }
}