타겟 넘버_복습

2026.08.03

문제 풀이

1차 실행 오류

---

실패 원인 분석
sum + numbers[i]의 과정에서 visited[i] = true후,
sum - numbers[i]의 과정에서 visited[i] == true 이기 때문에
값을 빼는 경우의 dfs가 동작하지 않음

또한 타겟 넘버는 모든 숫자를 다 더하거나 뺐을 경우에만 카운트해야 하는데,
해당 코드의 경우 중간 부분합의 경우도 더함

---

class Solution {
    private boolean[] visited;
    private int result = 0;
    public void dfs(int[] numbers, int sum, int target) {
        if (sum == target) {
            result++;
        }
        for (int i = 0; i < numbers.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            dfs(numbers, sum + numbers[i], target);
            dfs(numbers, sum - numbers[i], target);
        }
    }
    public int solution(int[] numbers, int target) {
        int len = numbers.length;
        visited = new boolean[len];
        dfs(numbers, 0, target);
        
        return result;
    }
}

AI 코드

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

문제 풀이 후기

이번 문제는 해결하지 못했다.

처음 공부할 때에도 재귀함수에 대해 큰 어려움이 있었고,
여전히 재귀함수에 대한 어려움이 있다.

나의 코드를 다시 한번 분석해보면,
근본적으로 코드에서 사용한 visited[] 를 사용할 필요가 없었다는 것이다.
위의 실패 원인에서 서술한 것 처럼
처음 visited[i] == true를 한 후, +연산과 -연산을 진행하게 되는데,
재귀적으로 진행하며 - 연산을 진행하지 않는 데에 있다.