[240403] 알고리즘 리부트 44일차 - 프로그래머스 타겟 넘버 자바

재귀..재귀..진짜 왜 재귀적 머리가 안 돌아가는지.. 한참 고민하고 푼 문제이다. 일단 타겟을 찾는 것보다 어쨋든 답이 나오는 문제라면 빼주어야 하는 값을 찾기로 한다. 오래 걸린 부분은 현재 이 숫자를 선택하느냐 마느냐라는 부분을 어떤 방식으로 구현하는 것인지였다.  아래와 같이 선택 여부에 따라 dfs를 나누어 실행해주고 만약 더한 값이 찾고자 하는 값보다 크면 바로 return해 버리는 방식으로 구현했다. 

class Solution {
    private static int find, answer;
    public int solution(int[] numbers, int target) {
        answer = 0;        
        int total = 0;
        
        for(int i =0; i<numbers.length; i++){
            total+=numbers[i];
        }
        
        find = (total-target)/2;
        dfs(0, numbers, 0);
  
        return answer;
    }
    
    private static void dfs (int thisNum, int [] numbers, int sum){    
        
         if(sum == find){            
            answer++;           
            return;
        } else if(sum > find) return;
        
      
        if(thisNum == numbers.length) return;

        int tmp = sum + numbers[thisNum];
        
        dfs(thisNum+1, numbers, tmp); //선택한 경우
        dfs(thisNum+1, numbers, tmp-numbers[thisNum]); //선택 안 한 경우
        
    }
}