[Programmers] 타겟 넘버 - JAVA

📚 Problem

타겟 넘버

• n개의 음이 아닌 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버 를 만들려고 합니다

📝 Solution

Key Idea

• DFS 를 이용하는데 덧셈으로 한번, 뺄셈으로 한번으로 총 두번의 재귀호출을 해줍니다
• 타겟 넘버와 같다면 개수를 카운트해줍니다

    private void DFS(int[] numbers, int target, int depth, int result) {
        if (depth == numbers.length) {
            if (result == target)
                answer++;
            return;
        }

        DFS(numbers, target, depth + 1, result + numbers[depth]);
        DFS(numbers, target, depth + 1, result - numbers[depth]);
    }

💻 Code

Solution.java

class Solution {
    private int answer;
    public int solution(int[] numbers, int target) {

        DFS(numbers, target, 0, 0);

        return answer;
    }

    private void DFS(int[] numbers, int target, int depth, int result) {
        if (depth == numbers.length) {
            if (result == target)
                answer++;
            return;
        }

        DFS(numbers, target, depth + 1, result + numbers[depth]);
        DFS(numbers, target, depth + 1, result - numbers[depth]);
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution(new int[]{1, 1, 1, 1, 1}, 3);
        assertEquals(5, result);
    }

    @Test
    public void solution_2(){
        int result = solution.solution(new int[]{4, 1, 2, 1}, 4);
        assertEquals(2, result);
    }
}