[Java, 자바] 프로그래머스 타겟 넘버

프로그래머스 

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

# 난이도 : LV2

# 알고리즘 분류 : DFS, BFS

---

문제내용

---

제한사항

---

입출력 예

---

풀이방법

이번 문제는 numbers 배열의 모든 경우의 수를 구하는 문제입니다 ! 추가적인 조건으로 더하기와 빼기가 골고루 섞여야한다는 점 !

DFS를 진행하기 위해서 매개변수로 Level과 누적합, 배열과 target을 매개변수로 전달하였습니다.

DFS를 호출할 때 L과 sum은 0을 초기값으로 전달해주고 DFS내부에서 다음 DFS로 호출할 때 L은 1을 더해주고, 더하기와 빼기가 모두 이루어져야하기 때문에 sum은 numbers[L] 값을 더한 값과 뺀 값을 따로 전달해주었습니다.

L의 값이 배열의 크기와 같아졌을 때 누적합이 target의 값과 같으면 answer을 증가시켜 마무리하였습니다 !

---

코드

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