⚡타겟 넘버

문제 설명

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

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

코드

스스로 해결하지 못하고 찾아본 풀이 코드이다. 참고

function solution(numbers, target) {
  let answer = 0;
  const length = numbers.length;

  function dfs(count, sum) {
    if (count === length) {
      if (target === sum) {
        answer++;
      }
      return;
    }

    dfs(count + 1, sum + numbers[count]); // 재귀함수(1)
    dfs(count + 1, sum - numbers[count]); // 재귀함수(2)
  }

  dfs(0, 0);

  return answer;
}

코드 풀이

문제에서 + - 의 조합을 통해 target의 값을 가지는 경우의 수를 구해야 했다.

그래서 DFS 탐색을 통해 모든 + - 를 조합하는 경우의 수를 구한 뒤, 해당 조합과 numbers 배열에 매치시켜 연산했을 때target에 해당하는 값과 일치하는 개수를 찾는 방식이다.

dfs(count, sum) 함수에서 count로 중단될 지점을 지정해주고, 숫자들의 합을 넘겨줄 sum 인수 두 가지를 지정하였다.

재귀 종료 조건

count 가 배열의 길이랑 같아지고, target 과 sum 의 값이 같다면 answer 의 값을 증가시키고 함수를 종료시키도록 되어있다.

재귀 실행 과정

dfs 함수에 count 를 +` 증가시키고, 연산자 '+'를 계산할 수 있도록 sum과 numbers의 숫자 하나를 꺼내 합을 계산한 값을 인수로 주고, '+'를 계산한 함수가 끝났다면 연산자 '-'를 계산할 수 있도록 sum과 numbers의 숫자 하나를 꺼내서 차이를 계산한 값을 인수로 주었다.

numbers = [4, 1, 2, 1], target = 4;

dfs(0,0);
dfs(count + 1, sum + numbers[count]); // 재귀함수(1) 
count = 0, sum = 0 → df(1, numbers[0]); // '+' 연산자
//
dfs(1, 4); count = 1; sum = 4; → dfs(2, 4+numbers[1]);
dfs(2, 5); count = 2; sum = 5; → dfs(3, 5+numbers[2]);
dfs(3, 7); count = 3; sum = 7; → dfs(4, 7+numbers[3]);
dfs(4, 8); count = 4; sum = 8; → 종료조건 count = numbers.length // 4+1+2+1 = 8
// 종료조건을 만나 재귀를 종료하고, target == sum 조건에 맞는다면 answer++
// 재귀함수(1)을 종료하고 종료되는 재귀를 부르는 시점으로 돌아가서 다음 코드를 실행한다.

// count = 3, sum = 7;
dfs(count+1, sum-numbers[count]); // 재귀함수(2) '-' 연산자
dfs(4, 6); count = 4; sum = 6; → 종료조건 count = numbers.length // 4+1+2-1 = 6

// 재귀 종료, 재귀를 부르는 시점으로 돌아가서 다음 코드 없으므로 다시 재귀함수(1) 실행
// count = 2; sum = 5; 
dfs(3, 3); count = 3; sum = 3; → dfs(4, 3+numbers[3]);
dfs(4, 4); count = 4; sum = 4; → 종료 // 4+1-2+1 = 4

// 종교 재귀 다음 코드 실행
// count = 3; sum = 3;
dfs(count+1, sum-numbers[count]); // 재귀함수(2) '-' 연산자
dfs(4, 2); → 종료 // 4+1-2-1 = 2
...

아직까지 직접 재귀함수를 짜는 것은 어려운 것 같다. 좀 더 많은 연습이 필요한 것 같다.