반응형
문제
설명
DFS로 풀었다.
dfs함수의 인자로 인덱스와 부호를 넘겨주었다.
1. 배열의 마지막 요소일 때 sum === target
이라면 answer
를 1
증가
2. 배열의 다음 요소를 +
일때와 -
일때 2개로 나누어 dfs로 호출한다.
코드
function solution(numbers, target) {
let sum = 0;
let answer = 0;
function dfs(i, sign) {
if (i === numbers.length - 1) {
if (sum === target) {
answer++;
}
} else {
//+
sum += numbers[i + 1];
dfs(i + 1, "+");
sum -= numbers[i + 1];
//-
sum -= numbers[i + 1];
dfs(i + 1, "-");
sum += numbers[i + 1];
}
}
//+
sum = numbers[0];
dfs(0, "+");
//-
sum = -numbers[0];
dfs(0, "-");
return answer;
}