(Java)프로그래머스 코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

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

2. 나의 풀이

import java.util.*;

class Solution {
    
    ArrayList <Integer> all_case = new ArrayList <Integer>();
    
    public int solution(int[] numbers, int target) {
        int j = 0;
        int plus = 0;
        int minus = 0;
        imsi(plus, minus, j, numbers, target);
        return all_case.size();
    }
    void imsi(int plus, int minus, int j, int [] numbers, int target) {
    	if(j == numbers.length) {
    		if(plus == target) {
    			all_case.add(plus);
    			return;
    		}else if(minus == target) {
    			all_case.add(minus);
    			return;
    		}else {
    			return;
    		}
    	}
    	plus += numbers[j];
    	minus -= numbers[j];
    	//System.out.println("plus : " + plus + ", minus : " + minus);
    	imsi(plus, plus, j + 1, numbers, target);
    	imsi(minus, minus, j + 1, numbers, target);
    }
}

3. 다른 사람 풀이

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = dfs(numbers, 0, 0, target);
        return answer;
    }
    int dfs(int[] numbers, int n, int sum, int target) {
        if(n == numbers.length) {
            if(sum == target) {
                return 1;
            }
            return 0;
        }
        return dfs(numbers, n + 1, sum + numbers[n], target) + dfs(numbers, n + 1, sum - numbers[n], target);
    }
}