[Java] level2 - dfsbfs_43165 : 타겟 넘버

문제 링크

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

풀이

로직 : dfs 활용

• numbers array에 주어진 숫자들을 플러스(+), 마이너스(-) 하면서 recursive를 활용해서 탐색해나가는 것이 핵심 => 이를 통해서 모든 경우의 수 확인 가능

static int dfs(int[] numbers, int n, int sum, int target) {
        if (n==numbers.length){
            if(sum==target){
                return 1; // recursive하니깐 1들을 합치면 몇가지로 가능한지 알 수 있음
            }
            return 0; // recusrisve 되는데 sum == target 안되는 애들은 count 안되게하기위해 return 0 해줌
        }
        return dfs(numbers, n+1, sum + numbers[n], target) + dfs(numbers, n+1, sum - numbers[n], target);