문제링크

풀이

DFS
시간복잡도: O($2^n$)
n개의 숫자가 있고, 각 숫자마다 더하거나 빼거나 두가지로 분기되기 때문이다.

재귀를 사용해서 DFS를 구현하는 기본적인 문제이다.
각 정수마다 더하거나, 빼거나 두 가지의 분기로 나뉘어 DFS를 수행한다.
모든 숫자를 사용했을 때(index가 배열의 길이과 같을 때) 연산을 수행한 sum 값이 target과 같으면 answer를 1 더하고 종료한다. target과 다르면 그냥 dfs를 종료한다.

코드

class Solution {
    static int answer = 0;

    public int solution(int[] numbers, int target) {

        dfs(numbers, 0, 0, target);
        return answer;
    }

    public static void dfs(int[] numbers, int index, int sum, int target) {
        if (index == numbers.length) {
            if (sum == target) {  //모든 수를 다 사용했고, 합이 타겟과 같으면 종료
                answer += 1;
                return;
            } else {
                return;
            }
        }
        dfs(numbers, index + 1, sum + numbers[index], target);
        dfs(numbers, index + 1, sum - numbers[index], target);
    }
}