DFS 연습 - 타겟넘버(JAVA)

[문제]
숫자 배열이 주어지면, 배열 숫자들을 더하거나 빼서 주어진 타겟 넘버로 만드는 경우의 수를 구하라.

문제 해결 코드

public class targetNumber {
    static int[] numbers = {1,1,1,1,1};
    static int target = 3;
    static int size = numbers.length;
    static int result = 0;
    public static void main(String[] args) {

        getResultdfs(0,0); //DFS코드
        System.out.println(result);
    }

    public static void getResultdfs(int index, int sum) {
        //종료조건
        if(index == size) {
            if(sum == target) {
                result++;
            }
           return ;
        }
        //구현내용
        //받은 인덱스 빼기
        getResultdfs(index+1, sum - numbers[index]);
        //받은 인덱스 더하기
        getResultdfs(index+1, sum + numbers[index]);

    }

문제 해결 방법

주어진 배열의 모든 숫자를 조합하는 경우를 생각해보면 결국 아래의 두가지 로직까지는 수행을 해야한다.
1. 모든 수를 다 더해보기
2. 모든 수를 다 빼보기

int[] numbers = {1,1,1};
int target = 1;

위와 같이 주어졌다고 가정했을 경우 모두 더하는 수부터, 모두 빼는 수까지 진행하여야한다.
(1) +1+1+1,
(2) +1+1-1,
(3) +1-1+1,
(4) +1-1-1,
(5) -1+1+1,
(6) -1+1-1,
(7) -1-1+1,
(8) -1-1-1

모든 숫자의 조합을 하나씩 조합하며 결과를 찾아가는 경우로 이런 문제는 DFS로 푼다.
전에 소개한 풀이 방식에서도 소개했듯 그려보면, 아래와 같이 3가지 경우의 수가 있단걸 알 수있다.