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

 

[광고 누르면 오늘의 행운 상승!!]

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

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

DFS 기본문제

1. 참고사항 

- +일경우, -일경우 2번 돌려야 한다.

2. 구현

- +일경우와 -일 경우로 나누어서 0번째 인덱스부터 배열의 사이즈까지 DFS를 돌린다.
- +일경우 더하고 -일경우 뺀다.
- cnt가 배열사이즈일 경우 target과 sum을 비교하여 같다면 ans를 증가시킨다.

종료.

import java.util.*;
import java.io.*;


class Solution {
    static int ans = 0;
    public int solution(int[] numbers, int target) {
        
        dfs(numbers,  numbers[0], 1, target);
        dfs(numbers, -numbers[0], 1, target);
        
        return ans;
    }
    private static void dfs(int[] numbers,int sum, int cnt, int target){
        if(cnt >= numbers.length){
            if(sum == target)
                ans++;
            return;
        }
        
        dfs(numbers,sum+numbers[cnt],cnt+1,target);
        dfs(numbers,sum-numbers[cnt],cnt+1,target);
    }
}