[프로그래머스 | lv.2 | DFS / BFS] 타겟넘버

타겟 넘버

✔ 아이디어
1. DFS 이용
- 배열에 담긴 수를 전부 사용해야함.
- 부호에 따라 선택할 수 있는게 나누어지기에 모든 경우의 수를 고려하려면 DFS 사용
2. 현재 숫자의 위치(INDEX == DFS의 DEPTH)를 기억해야함 이를 종료 조건으로 함.

class Solution {
    int result=0; // target을 만들 수 있는 방법의 수
    
    public void dfs(int sum, int index, int[] numbers, int target){
        if(index==numbers.length && sum==target){//전체 수를 다 쓰고, 합이 target과 같아지면
            result++;//방법의 수 증가
            return ;
        }
        if(index>=numbers.length){ // index outof range를 피하기 위함
            return ;
        }
        //부호 다르게해서 DFS
        dfs(sum+numbers[index], index+1, numbers, target);//합에 현재 인덱스 값을 더하고, 인덱스 증가시켜서 다시 dfs
        dfs(sum-numbers[index], index+1, numbers, target);//부호 다르게해서 다시 dfs
    }
    public int solution(int[] numbers, int target) {
        dfs(0,0,numbers, target);//시작위치 넣고 DFS
        return result;
    }
}