타겟 넘버

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 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

풀이

class Solution {
    int answer = 0;

    public int solution(int[] numbers, int target) {
        recursion(0, 0, target, numbers);
        return answer;
    }
    
    public void recursion(int index, int currentSum, int target, int[] numbers) {
        // 모든 숫자를 다 사용한 경우
        if (index == numbers.length) {
            if (currentSum == target) {
                answer++;
            }
            return;
        }

        // 현재 숫자를 더하거나 빼는 두 가지 경우로 재귀 호출
        recursion(index + 1, currentSum + numbers[index], target, numbers); // 현재 숫자를 더함
        recursion(index + 1, currentSum - numbers[index], target, numbers); // 현재 숫자를 뺌
    }
}

재귀를 사용하면 간단하게 풀수 있는 문제였다. 이전에 인덱스별로 타겟값과 비교하여 크면 빼고 작으면 더해야 하나? 이런생각으로 접근하려했었는데 경우의수를 다 빼거나 더해봐서 그 중 target값이 나오는 것을 찾는 완전 탐색 문제이므로 생각을 해보니 numbers 배열에 있는 값들을 더하거나 뺴는 것을 재귀문으로 모두 실행해보고 하나의 변수에 계속 업데이트 해준 뒤에 if문으로 만족하는 경우의수를 찾을 때마다 answer++를 해주어 구현할 수 있었다. 매개변수로는 모든 원소를 반복해서 더하거나 빼기위한 index, 계속 더하거나 빼는 값들을 누정해줄 currentSum, target, numbers배열로 설정해준 뒤 , if문에서 index가 numbers.length와 같을때 즉,  각각 더하고 빼는 두개의 재귀문이 계속 호출되다 마지막 원소까지 사용하였을때 값들을 업데이트 해놓은 currentSum을 target과 비교하여 같을 경우 정답인 경우의 수를 찾은 것이므로 answer을 1 증가 시켜 주어 구현할 수 있었다.   추가로 이전 문제들에서 재귀 함수에서 visited 배열을 사용하여 방문 여부를 체크하는 경우는 각 요소가 한 번만 사용되거나, 중복 사용을 방지해야 할 때 예를 들어, 그래프 탐색(DFS/BFS), 순열, 조합 계산과 같은 문제에서는 요소의 중복 사용을 방지해야 하므로 visited 배열이 필요했던 것이고 이 문제 같은경우에는 각 숫자에 대해 + 또는 - 연산을 적용할 수 있을 뿐, 각 숫자는 중복 사용하지 않기 때문에 별도의 불리안 타입 배열을 사용할 필요도 백트래킹을 해줄 필요도 없다는 것이다....