JavaScript로 목표 합계를 만족하는 숫자 조합 모두 찾기

문제 개요

JavaScript로 두 개의 인수를 받는 함수를 작성해야 합니다. 첫 번째 인수는 숫자 배열이며, 두 번째 인수는 목표가 되는 합계 값입니다.

함수는 배열에서 요소들을 선택해 그 합이 두 번째 인수로 전달된 값과 정확히 일치하도록 만들어야 하고, 조건을 충족하는 모든 숫자 조합을 배열 형태로 반환해야 합니다.

여기서 기억해야 할 두 가지 조건은 다음과 같습니다.

• 조합 내 숫자의 순서는 중요하지 않습니다.
• 필요하다면 같은 숫자를 여러 번 반복해서 사용할 수 있습니다.

입력 예시

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

const arr = [14, 6, 10];
const sum = 40;

이 경우 기대되는 출력은 다음과 같습니다.

const output = [
   [ 14, 14, 6, 6 ],
   [ 14, 6, 10, 10 ],
   [ 6, 6, 6, 6, 6, 10 ],
   [ 10, 10, 10, 10 ]
];

구현 코드

이 문제는 재귀와 백트래킹(backtracking) 기법을 활용하면 깔끔하게 해결할 수 있습니다. 각 단계마다 현재 숫자를 다시 선택하는 경우와 다음 숫자로 넘어가는 경우를 모두 탐색하는 방식입니다.

const arr = [14, 6, 10];
const sum = 40;
const findSum = (arr, sum) => {
    const res = [];
    const search = (index, part = []) => {
        const s = part.reduce((a, b) => a + b, 0);
        if (s === sum){
            res.push(part)
        };
        if (s >= sum || index >= arr.length){ return; };
        search(index, part.concat(arr[index]));
        search(index + 1, part);
    };
    search(0);
    return res;
}
console.log(findSum(arr, sum));

코드 동작 원리

• search 함수는 현재 탐색 위치(index)와 지금까지 선택한 숫자 목록(part)을 인자로 받습니다.
• reduce 메서드로 part의 합계를 계산한 뒤, 합계가 목표값과 일치하면 결과 배열에 해당 조합을 추가합니다.
• 합계가 이미 목표값 이상이거나 배열의 끝에 도달했다면 더 이상 탐색하지 않고 종료하여 불필요한 연산을 줄입니다.
• 재귀 호출은 두 갈래로 나뉩니다. 하나는 현재 숫자를 한 번 더 선택하는 경우(index 유지), 다른 하나는 다음 숫자로 진행하는 경우(index + 1)입니다. 덕분에 같은 숫자를 여러 번 사용하는 조합도 자연스럽게 탐색됩니다.

출력 결과

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

[
   [ 14, 14, 6, 6 ],
   [ 14, 6, 10, 10 ],
   [ 6, 6, 6, 6, 6, 10 ],
   [ 10, 10, 10, 10 ]
]