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

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

프로그래머스

 

기억해야할점들

첫번쨰, idx로 더하는 위치를 계속해서 가져가야합니다.

그래야만 중복해서 더하지않고 모두 각각 1번씩 더합니다.

두번째, dfs를 2가지 갈래로 나눕니다.

+와 - 밖에 없으니 그 두가지만 계산해주면 됩니다.

 

 

코드입니다.

import java.util.*;
class Solution {
    int Target;
    int[] Numbers;
    int answer = 0;
    public int solution(int[] numbers, int target) {
        Target = target;
        Numbers = numbers;
        dfs(0, 0, 0);
        return answer;
    }
    
    void dfs(int idx, int cnt, int sum){
        
        if(cnt == Numbers.length){
            if(Target == sum){
                // System.out.println(sum);
                answer += 1;
            }
            return ;
        }
        
        for(int i=idx;i<Numbers.length;i++){
            dfs(i+1, cnt + 1, sum + Numbers[i]);
            dfs(i+1, cnt + 1, sum - Numbers[i]);
        }
        
    }
}