출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다

---

문제

문제 분석

더하는 경우와 빼는 경우를 모두 구하여 target에 해당하는 경우가 몇개인지 구하는 경우입니다. 모든 수를 더하고 빼면서 경우의 수를 일일이 더해야 합니다.

---

풀이

나의 풀이

class Solution {
    
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        
        //재귀
        //-1 +1 +1 +1 +1
        //+1 -1 +1 +1 +1
        //+1 +1 -1 +1 +1
        //+1 +1 +1 -1 +1
        //+1 +1 +1 +1 -1
        
        
        //재귀 시작
        dfs(numbers, target, 0, 0);
        
        return answer;
    }
    
    //재귀
    public void dfs(int[] numbers, int target, int index, int sum){
        
        //종료 조건
        if(index == numbers.length){
            if(sum == target) answer++; //목표 수
            return;
        }
        
        //재귀 식
        //더했을 때
        dfs(numbers,target,index+1,sum+numbers[index]);
        //뺏을 떄
        dfs(numbers,target,index+1,sum-numbers[index]);
    }
}

answer를 필드로 두고 재귀 함수내에서 3구역으로 나누어 구현하였습니다.
종료 조건 + 더하는 경우 + 빼는 경우로
종료 조건은 문제에서 지시한대로 numbers의 모든 수를 연산하였을 때(=인덱스를 넘어갔을 때) 결과를 판단합니다.
target과 동일한 결과면 answer를 +1하여 갯수를 추가합니다.

더하는 경우와 빼는 경우 둘로 나누어 각각 재귀적으로 함수를 호출합니다.

강의의 풀이

class Solution {
    public int solution(int[] numbers, int target) {
        return sumCount(numbers,target,0,0); //재귀 시작
    }
    
    //재귀 함수
    int sumCount(final int[] numbers, final int target, int index, int sum){
        //종료 조건
        if(index == numbers.length){
            if(sum == target) return 1; //target이면 + 1추가
            return 0; //아니면 추가 안함
        }
        
        //더하는 경우
        //빼는 경우
        //target인 숫자의 갯수를 더함
        return sumCount(numbers, target, index + 1, sum + numbers[index]) +
            sumCount(numbers, target, index + 1, sum - numbers[index]);
    }
}

제가 풀었던 방법과 비슷 합니다.
종료 조건 + 더하는 경우 + 빼는 경우로 나누지만

answer이라는 필드에 결과를 저장하였던 방법과는 다르게, 재귀 함수내에서 결과들을 합하여 최종 반환시 결과를 가지게 됩니다.

더하는 재귀호출은 또 내부적으로 더하는 재귀호출과 빼는 재귀호출에서 target과 일치하는 경우의 갯수를 가지고 빼는 재귀호출도 내부적으로 더하는 재귀호출과 빼는 재귀호출에서 target과 일치하는 경우의 갯수를 가지고 와서 둘을 더하게 되면

재일 처음 호출된 재귀함수는 target과 일치하는 모든 경우의 수를 반환하게 됩니다.

---

GitHub

https://github.com/ds02168/Study_Algorithm/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%5BJava%5D%20%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/%ED%8C%8C%ED%8A%B88.%EA%B7%B8%EB%9E%98%ED%94%84%2CDFS%2CBFS/%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84.java