n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
function solution(numbers, target) {
var answer = 0;
function dfs(cur, target, rest) {
if(rest.length === 0) {
if(cur === target) answer++;
else return;
}
let next_rest = rest.slice(1);
dfs(cur+rest[0], target, next_rest);
dfs(cur-rest[0], target, next_rest);
}
dfs(-numbers[0], target, numbers.slice(1), 1);
dfs(numbers[0], target, numbers.slice(1), 1);
return answer;
}
나의 DFS에서는 레벨이 깊어질 때마다 앞으로 더하거나 빼야할 숫자가 들어있는 Array를 계속 파라미터로 넘겨줬는데, 그럴 필요 없이 numbers
배열의 인덱스와 길이의 관계를 가지고 재귀를 돌리면 나처럼 할 필요가 없다. (다른 사람 풀이)
function solution(numbers, target) {
let answer = 0;
getAnswer(0,0);
function getAnswer(x,value) {
if(x<numbers.length){
getAnswer(x+1,value + numbers[x]);
getAnswer(x+1,value - numbers[x]);
} else{
if(value === target){
answer++
}
}
}
return answer;
}
answer += 1
)까지 해줘야 한다면, 해당 변수를 nonlocal
키워드로 한 번 선언해주고 나서 수정작업을 진행해야 한다.def solution(numbers, target):
answer = 0
def dfs(current, level):
nonlocal answer
if level == len(numbers):
if current == target:
answer += 1
return
else:
dfs(current + numbers[level], level + 1)
dfs(current - numbers[level], level + 1)
dfs(0, 0)
return answer