타겟 넘버(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

끝까지 더하거나 빼서 target을 완성할 수 있는 경우의 수 구하기

 

---

 

풀이

 

접근 방식

1. dfs를 통한 모든 경우의 수 구하기

  → 재귀함수로 구현, length의 끝까지 도달했다면 return(exit)

  → 더하는 동작 실행 후 빼는 동작 실행

 

---

 

코드 리뷰

 

import java.util.*;

class Solution {
    int[] nums;
    int targetNum;
    int count = 0;
    public void dfs(int i, int sum) {
        if(i == nums.length) {	// 탈출조건은 length까지 도달했을 때가 된다.
            if(sum == targetNum) {	// 마지막까지 더하거나 뺏을 때 target과 같은지 비교
                count++;
            }
            return;
        }
        dfs(i + 1, sum + nums[i]);	// 더하는 동작을 실행
        dfs(i + 1, sum - nums[i]);	// 더하기 끝나면 빼는 동작을 실행
    }
    public int solution(int[] numbers, int target) {
        targetNum = target;
        nums = numbers;
        dfs(0, 0);
        return count;
    }
}

 

 

 

* refs

https://www.youtube.com/watch?v=S2JDw9oNNDk&t=349s