타겟 넘버_복습2

2026.09.26

문제 풀이

나의 코드

---

소요 시간: 25분
시간 복잡도: $O(2^N)$

---

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

AI 코드

---

시간 복잡도: $O(2^N)$

---

코드 분석

전체적인 구조는 동일하다.
매개변수로 전달하던 numbers, target 를 필드로 뺐다.

아래 코드는 cnt 를 없앤 코드로, 상태를 남기지 않아 더 깔끔하다.

---

class Solution {
    private int[] numbers;
    private int target;
    private int cnt = 0;

    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        dfs(0, 0);
        return cnt;
    }

    private void dfs(int idx, int sum) {
        if (idx == numbers.length) {
            if (sum == target) cnt++;
            return;
        }
        dfs(idx + 1, sum + numbers[idx]);
        dfs(idx + 1, sum - numbers[idx]);
    }
}

private int dfs(int idx, int sum) {
    if (idx == numbers.length) return sum == target ? 1 : 0;
    return dfs(idx + 1, sum + numbers[idx]) + dfs(idx + 1, sum - numbers[idx]);
}

문제 풀이 후기

이번 문제는 DFS의 가장 기본적인 문제 유형 중 하나로,
DFS에 대한 감을 다잡기 좋은 문제였다.