사용할 수 있는 숫자를 이용해 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 구해라.

→ 완전탐색의 DFS를 이용하여 모든 경우를 탐색하자.

• cnt = 현재까지 선택한 피연산자의 개수
• sum = 현재까지 선택한 피연산자의 누적 연산 결과

위의 두 변수를 재귀적으로 전달하여 numbers의 모든 수를 선택했을 때 누적 연산 결과(sum)이 타겟 넘버와 같다면 정답 결과를 더해주면 된다.

풀이 코드

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