JavaScript로 배열의 모든 조합 합계 구하는 방법

JavaScript에서 숫자 배열을 첫 번째 인수로, 그리고 숫자 n을 두 번째 인수로 받는 함수를 작성해야 하는 경우가 있습니다. 이때 n은 항상 배열의 길이보다 작거나 같다고 가정합니다.

이 함수는 원본 배열에서 길이가 n인 모든 가능한 부분 배열(조합)의 요소 합계를 담은 배열을 반환해야 합니다.

문제 예시

입력이 다음과 같다면:

const arr = [2, 6, 4];
const n = 2;

출력은 다음과 같아야 합니다:

const output = [8, 10, 6];

위 결과는 배열 [2, 6, 4]에서 길이 2인 조합인 [2, 6], [2, 4], [6, 4]의 각 합계인 8, 10, 6을 나타냅니다.

비트 마스크를 활용한 해결 방법

배열의 모든 부분 집합을 효율적으로 생성하려면 비트 마스크(bitmask) 기법을 사용할 수 있습니다. 길이가 L인 배열의 부분 집합 개수는 2^L개이며, 각 비트 조합이 특정 요소의 포함 여부를 결정합니다.

구현 코드는 다음과 같습니다:

const arr = [2, 6, 4];
const n = 2;
const buildCombinations = (arr, num) => {
    const res = [];
    let temp, i, j, max = 1 << arr.length;
    for(i = 0; i < max; i++){
        temp = [];
        for(j = 0; j < arr.length; j++){
            if (i & 1 << j){
                temp.push(arr[j]);
            };
        };
        if(temp.length === num){
            res.push(temp.reduce(function (a, b) { return a + b; }));
        };
    };
    return res;
}
console.log(buildCombinations(arr, n));

코드 설명

위 코드의 동작 방식을 단계별로 살펴보겠습니다:

1. 전체 경우의 수 계산: max = 1 << arr.length는 2^3 = 8을 의미하며, 배열의 모든 부분 집합 개수에 해당합니다.

2. 비트 검사: 외부 루프의 변수 i는 하나의 비트 마스크 역할을 하고, 내부 루프에서 i & 1 << j 연산으로 j번째 요소를 현재 조합에 포함할지 판단합니다.

3. 조건 필터링: 생성된 조합의 길이가 목표 값 num과 일치할 때만 reduce() 메서드로 요소들의 합을 계산하여 결과 배열에 추가합니다.

실행 결과

콘솔 출력 결과는 다음과 같습니다:

[ 8, 6, 10 ]

출력 순서는 비트 마스크 탐색 순서에 따라 달라질 수 있지만, 길이가 2인 모든 조합의 합계(8, 10, 6)가 정확히 포함되어 있는 것을 확인할 수 있습니다.

시간 복잡도 고려 사항

이 방법의 시간 복잡도는 O(2^L × L)입니다. 따라서 배열의 길이가 매우 큰 경우에는 슬라이딩 윈도우(sliding window)나 재귀적 백트래킹(backtracking) 기법을 사용하는 것이 더 효율적일 수 있습니다. 다만 배열 길이가 짧거나 모든 조합을 명확하게 확인해야 하는 상황에서는 위의 비트 마스크 접근법이 직관적이고 유용합니다.