1. 문제

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때
숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return한다

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

2. 아이디어

처음에 return값 answer을 0으로 초기화하고 DFS로 배열의 각 인덱스의 값을 더하거나 빼고 배열의 끝에 도달했을 때 총 값이 target과 같다면 count를 1 증가시킨다.

3. 코드

public class targetNumber {

    public static int dfs(int[] input, int m, int target, int index){
        if(index >= input.length){
            //return m == target ? 1 : 0;
            if(m == target){
                return 1;
            }
            else return 0;
        }
        else{
            //트리처럼 나눠지고 최종 Leaf에서 조건을 만족하는 경우 1을 리턴하므로 그 1을 모두 더하면 된다
            return dfs(input, m+input[index], target, index+1) 
            + dfs(input, m-input[index], target, index+1);
        }
    }

    public static int solution(int[] numbers, int target) {
        int answer = 0;

        answer = dfs(numbers, 0, target, 0);

        return answer;
    }

    public static void main(String[] args) {

        int[] input = {1,1,1,1,1};
        int target = 3;

        System.out.println(solution(input, target));

    }
}

4. end...

아직 DFS, BFS 문제를 푸는 감이 부족한 거 같다
재귀가 되었을 때 어떻게 동작할지가 머리 속에 쉽게 구상이 되지 않는다🤦🏻‍♂️
계속 풀어보며 그 감을 익혀야겠다 이건 정말 기본 문제니깐...😓