JavaScript에서 합이 동일한 n개의 하위 배열 찾기

이번 글에서는 정수 배열과 하나의 정수를 인수로 받는 JavaScript 함수를 작성해 보겠습니다. 이 함수의 목표는 원본 배열을 두 번째 인수로 전달된 개수(n개)의 하위 배열(부분 집합)로 나눌 수 있는지 확인하고, 모든 하위 배열의 합이 서로 동일한 경우 true를 반환하는 것입니다.

문제 이해하기

예를 들어 입력값이 다음과 같다고 가정해 보겠습니다.

const arr = [4, 3, 2, 3, 5, 2, 1];
const num = 4;

이 경우 출력은 true가 되어야 합니다. 왜냐하면 배열을 다음과 같은 네 개의 하위 배열로 나눌 수 있고, 각각의 합이 모두 5로 같기 때문입니다.

[5], [1, 4], [2, 3], [2, 3]

접근 방법

이 문제는 대표적인 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 해결 과정은 다음과 같습니다.

먼저 배열 전체의 합을 구합니다. 만약 전체 합이 n으로 나누어 떨어지지 않는다면, 애초에 합이 동일한 n개의 그룹을 만드는 것이 불가능하므로 즉시 false를 반환합니다.

나누어 떨어진다면, 각 하위 배열이 가져야 할 목표 합(target)은 '전체 합 ÷ n'이 됩니다. 이후 재귀적으로 요소들을 하나씩 배치하면서, 각 그룹의 합이 목표 값에 도달하면 다음 그룹 채우기로 넘어가는 방식으로 탐색을 진행합니다. 이미 사용된 요소는 visited 배열로 표시하여 중복 사용을 방지합니다.

구현 코드

다음은 위 로직을 구현한 전체 코드입니다.

const arr = [4, 3, 2, 3, 5, 2, 1];
const num = 4;
const canFormSubarray = (arr = [], num) => {
   const total = arr.reduce((sum, num) => sum + num, 0);

   // 전체 합이 n으로 나누어 떨어지지 않으면 불가능
   if (total % num !== 0) {
      return false;
   }
   const target = total / num;
   const visited = new Array(arr.length).fill(false);
   const canPartition = (start, numberOfSubsets, currentSum) => {
      // 마지막 그룹은 자동으로 성립
      if (numberOfSubsets === 1) {
         return true;
      }
      // 현재 그룹의 합이 목표에 도달하면 다음 그룹으로 이동
      if (currentSum === target) {
         return canPartition(0, numberOfSubsets - 1, 0);
      };
      for (let i = start; i < arr.length; i++) {
         if (!visited[i]) {
            visited[i] = true;
            if (canPartition(i + 1, numberOfSubsets, currentSum + arr[i])) {
               return true;
            }
            visited[i] = false;
         };
      };
      return false;
   };
   return canPartition(0, num, 0);
};
console.log(canFormSubarray(arr, num));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

true

코드 설명

reduce() 메서드를 사용해 배열의 전체 합을 계산하고, 이 값이 num으로 나누어 떨어지지 않으면 바로 false를 반환합니다. 나누어 떨어지는 경우에는 목표 합인 target을 구한 뒤, 내부 함수 canPartition을 통해 백트래킹 탐색을 시작합니다.

canPartition 함수는 세 개의 매개변수를 받습니다. 탐색을 시작할 인덱스(start), 남은 하위 배열의 개수(numberOfSubsets), 그리고 현재까지 채운 그룹의 합(currentSum)입니다. 남은 그룹이 하나뿐이라면 나머지 요소들이 자동으로 마지막 그룹을 이루므로 true를 반환하고, 현재 그룹의 합이 목표에 도달하면 새로운 그룹 채우기를 시작합니다.

요소를 선택할 때는 해당 요소를 visited로 표시한 후 재귀 호출을 진행하고, 성공하지 못하면 표시를 해제하여 다른 조합을 시도합니다. 이러한 백트래킹 과정을 통해 가능한 모든 조합을 효율적으로 탐색할 수 있습니다.