문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

입출력

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

예시

[1,1,1,1,1]
-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

코드

의사 코드

• 모든 값을 더한 후 만일 값이 맞지 않는 경우 다시 돌아와 lever별로 하나씩 빼 보면서 나아간다.
  (재귀를 이용한 DFS)

function solution(numbers, target) {
  let answer = 0;
  const length = numbers.length;
  
  function DFS(L, sum) {
    if (L === length) {
      if (sum === target) {
        answer++;
      }
    } else {
      DFS(L + 1, sum + numbers[L]);
      DFS(L + 1, sum - numbers[L]);
    }
  }

  DFS(0, 0);
  return answer;

}

• 먼저 DFS의 첫 번째 if문은 재귀를 멈추는 조건문으로 모든 값(모든 레벨L)을 더 했을때 sum의 값이 target값과 같은 경우 answer의 값을 카운팅해준다.
• else문 안에 DFS(L + 1, sum + numbers[L]); 와 DFS(L + 1, sum - numbers[L]); 는 처음 DFS로 진입해 모든 레벨들을 더하고 난 뒤 다음 DFS로 진입해 모든 레벨에 한 번씩 빼는 재귀를 반복해준다.

[1,1,1,1,1]
-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

• 위의 예시 처럼 모든 값을 더해보고 다시 한 레벨씩 내려가면서 다시 빼는 작업을 반복해주는 구문이 위의 else문의 역할이다.