[프로그래머스/JAVA] - 타겟 넘버

코딩테스트 연습 - 타겟 넘버 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

풀이

class Solution {
    int answer = 0;
    public int solution(int[] numbers, int target) {
        
        dfs(numbers,0,target,0);       
        
        return answer;
    }
    
    public void dfs(int[] numbers, int depth, int target, int sum){
        
        if(numbers.length == depth){
            if(target==sum) answer++;            
        }else{
            dfs(numbers,depth+1, target, sum+numbers[depth]);
            dfs(numbers,depth+1, target, sum-numbers[depth]);
        }
    }
}

 

깊이우선 dfs를 이용

 

ex)

 

numbers = {4, 1, 2, 1}

target = 4

return = 2

depth = 1 

sum

4

-4

 

depth = 2 

sum

5

3

-3

-5

 

depth = 3

sum

7

3

5

1

-1

-5

-3

-7

 

depth = 4   

sum 

8

6

4

2

6

4

2

0

........

-8