[프로그래머스] 타겟 넘버 43165 (JAVA)

풀이 방식

main

깊이 우선 탐색 depthFirstSearch 메소드 호출

depthFirstSearch

• 종료 조건:
  이번에 부른 숫자가 마지막 인덱스인 경우,
  '총합 == target'일 때 숫자 세기 (return 1)
• 점화식:
  마지막 인덱스가 아닌 보통의 경우,
  더하는 경우와 빼는 경우 각각 재귀호출하여 결과 합산

포인트

점화식

dfs(변수들, , , sum + numbers[index]) + dfs(변수들, , , sum - numbers[index])

return 
	depthFirstSearch(numbers, target, index+1, sum + numbers[index]) 
    + depthFirstSearch(numbers, target, index+1, sum - numbers[index]);

주어진 숫자는 순서를 바꾸지 않고 오로지 빼거나 더할 수만 있으므로,
각 숫자를 더했을 때의 경우와 뺐을 때의 경우를 각각 호출해서 그 결과를 합함

구현

public class NUM43165 {
    public static void main(String[] args) {
        int[] numbers = {4, 1, 2, 1};
        int target = 4;

        System.out.println(solution(numbers, target));
    }

    public static int solution(int[] numbers, int target) {
        int answer = 0;
        answer = depthFirstSearch(numbers, target, 0, 0);

        return answer;
    }

    public static int depthFirstSearch(int[] numbers, int target, int index, int sum){
        if(index == numbers.length) {
            if(sum == target) return 1;
            else return 0;
        }
        
        return depthFirstSearch(numbers, target, index+1, sum + numbers[index]) + depthFirstSearch(numbers, target, index+1, sum - numbers[index]);
    }
}

---

*다른 분들의 코드를 참고하여 작성했습니다