프로그래머스 타겟 넘버

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

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

[문제 설명]

 

 

 

DFS (깊이 우선 탐색)을 이용하여 음수 양수의 경우를 고려해 그래프 탐색을 해주면 됩니다.

 

 

 

1. 시작점을 0으로한 dfs 시작
2. 만약 리프 노드가 아니라면 idx+1을 해주고, 현재 노드의 값과 누적 합계를 더한다.
3. 음수 양수 dfs를 돌려준다.
4. 만약 리프 노드이면서 찾으려는 값을 찾았다면 count 값을 증가 한다.
5. dfs가 종료 되고 나면 찾으려는 값 만큼 count 되어 있으므로 return 한다.

 

class Solution {
    int count;
    public int solution(int[] numbers, int target) {

     dfs(0,target, 0, numbers);

        return this.count;
    }

    public void dfs(int idx,int target, int sum, int[] numbers){
        if(idx == numbers.length){
            if(sum == target) this.count++;
            return;
        }
        dfs(idx + 1, target, sum + numbers[idx],numbers);
        dfs(idx + 1, target, sum - numbers[idx],numbers);
    }
}