문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43165
문제 접근
재귀함수를 이용한 DFS 알고리즘으로 접근을 했다.
DFS를 이용해야겠다는 생각은 했지만 stack을 이용한 DFS로 처음에 접근했다.
약간의 힌트를 통해 재귀함수로 방향을 바꾸었으나, dfs
메소드 반환형을 int
로 해야한다는 강박에 return
조건을 어떻게 설정해야하나 고민했었다.
결국 다른 분의 코드를 참고하여 반환형을 void
로 바꾸고 idx
값 비교와 sum
값 비교를 통해 문제를 해결할 수 있었다.
핵심
void
idx
값이 배열 끝에 도달했을 때, sum
이 target
과 같은지 비교소스 코드
class Solution {
int answer;
public int solution(int[] numbers, int target) {
answer = 0;
dfs(numbers, target, 0, '+', 0);
dfs(numbers, target, 0, '-', 0);
return answer;
}
public void dfs(int[] numbers, int target, int sum, char ch, int idx) {
switch (ch) {
case '+':
sum += numbers[idx];
break;
case '-':
sum -= numbers[idx];
break;
}
if (idx == (numbers.length - 1)) {
if (sum == target) {
answer++;
}
} else {
dfs(numbers, target, sum, '+', idx + 1);
dfs(numbers, target, sum, '-', idx + 1);
}
}
}