프로그래머스 타겟 넘버

문제설명

생각하기

1. 깊이우선 탐색을 사용하여 문제풀기
2. dfs 함수를 만들어 순차적으로 +,-를 해주기
3. dfs함수가 끝났을 때 sum == target이라면 ans++해주기

내 풀이

class Solution {
    int ans = 0;
    public int solution(int[] numbers, int target) {
        
        dfs(numbers,0,0,target);
        return ans;
    }
     //n = 수행한횟수(노드깊이) sum= 연산수행값
    public void dfs(int[] numbers, int n, int sum, int target){
        if(n == numbers.length){
            if(sum == target) ans++;
        }else{
            dfs(numbers, n+1 , sum + numbers[n], target);
            dfs(numbers, n+1 , sum - numbers[n], target);
        }
        
    }
}


else문에서 첫번째 dfs문을 수행할 때 결과값 ( numbers는 입출력 예 2번째 값 [4,1,2,1])
  				dfs( 1 , 4 ) 
    			  (2, 5)(2,3)   
			  (3,7)(3,3) (3,5)(3,1)
(4,8)(4,6)(4,4)<++ (4,2)  (4,6)(4,4)<++ (4,2)(4,0)
두번의 증가로 ans는 2가 된다.
두번째 dfs의 수행결과엔 sum==target인 경우는 없다.