타겟넘버

📍 문제 설명

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

코딩테스트 연습 - 타겟 넘버

 

💡 접근

다 더하는거 ~ 다 빼는거 중에서 target인 숫자 찾는 DFS 문제

 

👩‍💻 코드

import java.util.*;

class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static char[] c = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    static int[] arr;
    static char[] arr2;
    static HashMap<Character, Integer> map;
    static boolean[] visited;
    static int[] clone;
    static int answer;

    public int solution(int[] numbers, int target) {
        clone = numbers;
        visited = new boolean[numbers.length];
        DFS(0, 0, target);
        System.out.println(answer);
        return answer;
    }

    private void DFS(int L, int sum, int target) {
        if(L == clone.length) {
            if(target == sum) {
                answer++;
            }
        }
        else {
            DFS(L+1, sum+clone[L], target);
            DFS(L+1, sum-clone[L], target);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();

        int[] numbers = {1, 1, 1, 1, 1};
        int target = 3;
        s.solution(numbers, target);
    }
}