프로그래머스 Lv2 타겟넘버 Java

문제설명

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

구현방법

• 기본적인 dfs로 구현이 가능하다. 0부터 시작해서 numbers[index]를 더하고 빼는 과정을 재귀로 탐색하고 numbers를 모두 사용했을 때 타겟넘버와 sum이 같다면 문제가 해결된다.
• dfs를 사용할땐 함수 내에 인자를 늘리는 것 보다 전역변수로 설정하는 것이 편해서 전역변수로 다 옮겼음.

코드

class Solution {
    static boolean use[];
    static int nums[];
    static int tg;
    static int cnt;
    static int sum=0;
    public int solution(int[] numbers, int target) {
        cnt = 0;
        nums = numbers;
        use = new boolean[numbers.length];
        tg = target;
        dfs(0,0);
        return cnt;
    }
    public void dfs(int sum,int start){
        if(start==nums.length){
            if(sum==tg){
                cnt++;    
            }
            return;
        }
        dfs(sum+nums[start],start+1);
        dfs(sum-nums[start],start+1);
    }
}