[Algorithm][Programmers] 타겟 넘버 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

입출력 예시

풀이

모든 경우의 수를 봐야하기 때문에 재귀 함수를 사용했습니다.

sum을 0으로 설정하고 numbers의 값의 순서가 일정하기 때문에 차례대로 index를 늘려가면서 sum에 더하거나 빼주는 식으로 재귀 함수를 작성하여 풀이하였습니다.

재귀에서 if문을 활용하여 numbers[]의 길이만큼 탐색했을 때 return하고 sum값이 target값과 동일하면 1을 반환하여 더해주었습니다.

코드

class Solution {
    public int solution(int[] numbers, int target) {        
        int answer = recur(numbers, 0, 0, target);
        return answer;
    }
    public int recur(int[] numbers, int index, int sum, int target) {
        if(index == numbers.length) {        
            if(sum == target) {
                return 1;
            }
            return 0;
        }
        return recur(numbers, index + 1, sum + numbers[index], target)
            + recur(numbers, index + 1, sum - numbers[index], target);
    }
}

제한 사항