프로그래머스 - 타겟 넘버(Java)

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

재귀 알고리즘을 활용하여 아주 쉽게 풀수 있는 문제이다.

 

※주의 해야할 점

1. 순서를 바꾸면서 계산하지 않기 때문에 계산의 시작점을 다르게 하거나 뒤로 돌아가는 경우를 구할 필요 없이 선형적으로 뻗어 나가면 된다.
2. 선형적으로 앞으로만 뻗어나가면서 계산하면 되기 때문에 방문여부를 따지는 Visit 배열은 필요없다.

<코드>

import java.util.*;

class Solution {
    static int count =0;
    public int solution(int[] numbers, int target) {
        int answer = 0;
        dfs(numbers,target,0,0);
        answer=count;
        return answer;
    }
    public static void dfs(int[] numbers,int target,int value,int start){
        if(start==numbers.length){
            if(value==target){
                count++;
            }
            return;
        }
       
                dfs(numbers,target,value+numbers[start],start+1);
                dfs(numbers,target,value-numbers[start],start+1);
            
        }
}