[프로그래머스] 43165. 타겟 넘버

문제 링크

[프로그래머스] 43165. 타겟 넘버

풀이 과정

문제에서 주어진 숫자 배열에 +와 - 연산을 임의로 사용하여 target 숫자를 만드는 경우의 수가 몇 개인지를 출력하는 문제입니다.

배열 각각의 요소를 더했을 때, 뺐을 때의 누적 값을 파라미터로 전달하면서 재귀 함수를 호출하고, 끝에 도달하면 카운트를 증가시키는 방법으로 문제를 풀었습니다.

코드

public class Main {
    static int cnt;

    public static int solution(int[] numbers, int target) {
        dfs(1, numbers[0], numbers, target);
        dfs(1, -numbers[0], numbers, target);

        return cnt;
    }

    public static void dfs(int idx, int sum, int[] numbers, int target) {
        if (idx == numbers.length) {
            if (sum == target)
                cnt++;

            return;
        }

        dfs(idx + 1, sum + numbers[idx], numbers, target);
        dfs(idx + 1, sum - numbers[idx], numbers, target);
    }

    public static void main(String[] args) {
        int[] numbers = {1, 1, 1, 1, 1};
        int target = 3;

        solution(numbers, target);
    }
}