JavaScript로 배열을 합이 동일한 두 하위 배열로 분할할 수 있는지 확인하는 방법

정수 배열을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수의 역할은 주어진 배열을 두 개의 하위 배열로 나누었을 때, 각 하위 배열에 포함된 요소들의 합이 서로 같아지는 경우가 존재하는지 판단하는 것입니다. 단, 원본 배열의 요소를 분할하는 과정에서 어떤 요소도 남기지 않고 반드시 모두 사용해야 한다는 조건이 있습니다.

문제 이해하기

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

const arr = [5, 3, 7, 4, 1, 8, 2, 6];

이때 함수가 반환해야 하는 결과는 다음과 같습니다.

const output = true;

그 이유는 원하는 하위 배열인 [5, 3, 4, 6]과 [7, 1, 8, 2]가 모두 합이 18로 동일하기 때문입니다.

접근 방식

이 문제는 대표적인 부분집합 합(Subarray Sum) 문제로, 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.

• 먼저 배열 전체의 합을 구합니다. 전체 합이 홀수라면 두 부분으로 균등하게 나누는 것 자체가 불가능하므로 즉시 false를 반환합니다.
• 전체 합이 짝수라면 목표값(target)은 전체 합의 절반이 됩니다. 따라서 문제는 '합이 target이 되는 부분집합이 존재하는가?'로 바뀝니다.
• 부울(Boolean) 배열을 활용해 각 합계 값이 만들어질 수 있는지 여부를 추적하며, 순회 과정에서 목표값에 도달 가능하면 true를 반환합니다.

예제

다음은 위 접근 방식을 구현한 코드입니다.

const arr = [5, 3, 7, 4, 1, 8, 2, 6];
const canPartition = (arr = []) => {
   const sum = arr.reduce((acc, val) => acc + val);
   if (sum % 2 !== 0){
      return false;
   };
   const target = sum / 2;
   const array = new Array(target + 1).fill(false);
   array[0] = true;
   for (const num of arr) {
      if (array[target - num]){
         return true
      };
      for (let i = target; i >= num; i--) {
         array[i] = array[i - num];
      }
   }
   return false;
};
console.log(canPartition(arr));

출력 결과

위 코드를 실행했을 때 콘솔에 출력되는 결과는 다음과 같습니다.

true

이처럼 동적 계획법을 활용하면 배열을 합이 동일한 두 하위 배열로 분할할 수 있는지 O(n × target)의 시간 복잡도로 효율적으로 판별할 수 있습니다.