💡 문제
💬 입출력 예시
📌 풀이(소스코드)
class Solution {
static int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, target, 0, numbers.length, 0);
return answer;
}
public void dfs(int[] numbers, int target, int depth, int n, int sum) {
if (depth == n) {
if (sum == target) {
answer++;
}
return;
}
dfs(numbers, target, depth + 1, n, sum + numbers[depth]);
dfs(numbers, target, depth + 1, n, sum - numbers[depth]);
}
}
📄 해설
접근
- DFS 기본 문제
- 각 숫자를 확인하면서 다음 숫자를 더하는 경우와 빼는 경우로 가지를 펼쳐서 수행하면 된다.
- 모든 숫자를 사용했을 때, 그 시점의 합과 타겟 넘버의 값을 비교하면 된다.
- DFS 에 대한 개념만 잘 잡아놓으면 된다. DFS 의 핵심은 가치 뻗기
과정
dfs
메소드를 호출
- 현재까지 사용된 숫자의 개수인
depth
가 전체 숫자의 개수인 n
과 같다면, 모든 숫자를 사용한 것이므로 현재까지의 결과인 sum
과 target
의 동등 비교를 수행
- 같으면
answer
의 값 증가. 다르면 그냥 종료
depth == n
이 아니라면 두개의 dfs
메소드를 재귀호출한다.
- 하나는 다음 숫자를 더하는 경우
- 하나는 다음 숫자를 빼는 경우