[코딩테스트]프로그래머스 - 타겟 넘버

타겟 넘버

문제 설명

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 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers			target		return
[1, 1, 1, 1, 1]		3		5

입출력 예 설명

문제에 나온 예와 같습니다.

해결한 코드

function solution(numbers, target){
  var answer = 0
  var result = dfs(numbers, target, 0, answer)
  return result
}
function dfs(numbers, target, num, answer){
  var newArr = [...numbers]
  var temp = newArr.pop()
  if(numbers.length == 0){
    if(target == num){
       	answer++
    }
    return answer
  } else {
    answer = dfs(newArr, target, num+temp, answer) + dfs(newArr, target, num-temp, answer)
  }
  return answer
}

알고리즘

1. 재귀를 사용한다.
   1-1. numbers의 마지막 원소를 뺀다.
   1-2. 이 마지막 원소를 +1 또는 -1 하며 재귀를 돌린다. (num과 더해주거나 빼줌)
   1-3. numbers로 들어온 배열의 길이가 0이 되면 재귀를 끝낸다.
2. 이 값이 target과 같으면 answer를 추가해준다.
3. answer를 반환한다.

결국 모~~~든 경우의 수를 다 구한 다음에 개수를 세어주는 방식이다.
코딩테스트에 재귀가 빠질 수 없는 만큼 재귀를 참 잘 이해하고 싶은데, 막상 혼자 짜려고 하면 너무 어렵다 ㅜㅜ 흐엉엉

재귀를 짤때,
1. 끝내는 조건
2. return 하는 값이 어떻게 쓰이나
이 둘을 반드시 명심해주고 짜야 함을 잊지 말자 !!

추가로) reduce로 재귀를 짤 땐 배열의 길이를 splice || slice를 이용하여 끝내는 지점을 설정해주었던 걸 잊지 말자 !