[프로그래머스] 타겟 넘버

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

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

---

 

풀이

DFS를 이용해서 문제를 해결했다. 첫번째 원소부터 마지막 원소까지 탐색을 하면서, 해당 원소를 덧셈했을때와 뺄셈했을때의 경우를 모두 구해준 뒤, 마지막 원소까지 탐색을 했고 그 경우에 target과 같다면 answer를 +1 해준다.

 

시간복잡도

숫자의 개수는 2~20개 이고, 각 원소마다의 경우의 수는 2가지의 경우이므로 , O(2²⁰)이 된다.

 

코드

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