JavaScript로 목표 합계를 만드는 모든 조합 구하기 – 숫자 중복 사용 허용

이번 글에서는 첫 번째 인자로 숫자 배열을, 두 번째 인자로 목표 합계(target sum)를 받는 JavaScript 함수를 작성해 보겠습니다.

이 함수의 역할은 원본 배열에서 가져온 요소들의 합이 정확히 목표 합계가 되는 모든 하위 배열(subarray)을 찾아 배열 형태로 반환하는 것입니다. 특별한 점은 같은 숫자를 여러 번 반복해서 사용할 수 있다는 조건입니다.

문제 이해하기

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

const arr = [1, 2, 4];
const sum = 4;

그렇다면 기대되는 출력 결과는 아래와 같습니다. 각 하위 배열의 요소를 모두 더하면 4가 됩니다.

const output = [
    [1, 1, 1, 1],
    [1, 1, 2],
    [2, 2],
    [4]
]

접근 방식

이 문제는 전형적인 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.

현재까지 선택한 숫자들의 합이 목표 합계와 같으면 결과에 저장하고 종료하고, 합계가 목표보다 커지거나 배열의 끝에 도달하면 해당 탐색 경로를 포기합니다. 그리고 각 단계에서 두 가지 선택지를 고려합니다. 바로 현재 인덱스의 숫자를 한 번 더 사용하는 경우(중복 사용 허용)와 다음 인덱스로 넘어가는 경우입니다.

구현 코드

const arr = [1, 2, 4];
const sum = 4;

const getCombinations = (arr = [], sum) => {
    const result = [];
    const pushElement = (i, t) => {
        // 현재까지 선택한 숫자들의 합계 계산
        const s = t.reduce(function (a, b) {
            return a + b;
        }, 0);
        // 합계가 목표와 일치하면 결과에 추가
        if (sum === s) {
            result.push(t);
            return;
        }
        // 합계 초과 또는 배열 끝 도달 시 백트래킹
        if (s > sum || i === arr.length) {
            return;
        }
        // 현재 숫자를 다시 사용하는 경우
        pushElement(i, t.concat([arr[i]]));
        // 다음 숫자로 넘어가는 경우
        pushElement(i + 1, t);
    }
    pushElement(0, []);
    return result;
};

console.log(getCombinations(arr, sum));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[ [ 1, 1, 1, 1 ], [ 1, 1, 2 ], [ 2, 2 ], [ 4 ] ]

정리

이 알고리즘은 재귀 호출을 통해 모든 가능한 조합을 탐색하며, 불필요한 경로는 합계 비교만으로 빠르게 가지치기(pruning)하기 때문에 효율적입니다. 동일한 숫자를 반복 사용할 수 있어야 하는 조합 문제(예: 동전 교환 문제의 조합 버전)에서 널리 활용되는 패턴이므로, 백트래킹 학습의 좋은 출발점이 됩니다.