코드
function solution(numbers, target) {
let ans = 0;
dfs(0, 0)
function dfs(index, sum) {
if(index < numbers.length) {
dfs(index+1, sum+numbers[index]);
dfs(index+1, sum-numbers[index]);
}
else {
if(sum === target) ans++
}
}
return ans;
}
DFS(깊이우선탐색)
- 어떤 알고리즘인지도 알고, 코드도 아는데 활용을 어떻게 하는지 항상 몰랐어요! 하지만 이제 알았쬬오오오오오!!! 이 문제 솔직히 못 풀었는데 배웠다는 것만으로도 구글이 바라는 인재가 아닐까요?^__^
- 깊이우선 탐색은 root 노드부터 시작해 왼쪽 끝까지 들어갔다가 올라오고 다시 끝까지 들어가고? 암튼 한 번 들어갔다간 끝장보며 탐색하는 알고리즘이에요. 암튼 난 이해했음~
- 주어진 숫자를 모두 더하거나 빼야하는데 그 경우의 수를 깊이우선 탐색 알고리즘으로 짰다.
- index와 sum을 0부터 시작하는 dfs(0, 0) 그 다음부터 numbers 숫자들을 파고 들어가요!
재귀함수
- dfs에서는 재귀함수를 사용하여 탐색을 해요!
- index가 numbers.lnegth와 같아지고 sum과 target이 같아지면 ans를 ++ 해준다.
참고 사이트