JavaScript에서는 요소 개수가 서로 다른 여러 개의 배열이 주어졌을 때, 각 배열에서 하나의 요소씩 선택해 만들 수 있는 모든 조합을 생성해야 하는 경우가 자주 있습니다. 이번 글에서는 배열의 개수와 길이가 유동적이어도 동작하는 범용 조합 생성 함수를 재귀(Recursion)를 활용해 구현하는 방법을 알아보겠습니다.
문제 이해하기
예를 들어 다음과 같은 데이터가 있다고 가정해 보겠습니다.
const arr = [ [0,1], [0,1,2,3], [0,1,2] ]
위 데이터는 요소 개수가 각각 2개, 4개, 3개로 서로 다른 3개의 하위 배열로 구성되어 있습니다. 우리가 원하는 것은 각 배열에서 하나의 요소씩 뽑아 만들 수 있는 모든 조합을 구하는 것입니다.
결과는 다음과 같은 형태가 됩니다.
0,0,0 // 첫 번째 배열의 0, 두 번째 배열의 0, 세 번째 배열의 0 0,0,1 0,0,2 0,1,0 0,1,1 0,1,2 0,2,0 0,2,1 0,2,2
이런 식으로 마지막 조합인 1,3,2까지 계속 이어집니다.
배열 개수가 고정되지 않은 경우
만약 배열의 개수가 항상 고정되어 있다면 중첩 반복문을 사용해 하드코딩으로도 쉽게 구현할 수 있습니다. 하지만 실제 상황에서는 배열의 개수가 얼마든지 달라질 수 있습니다.
const arr1 = [[0,1], [0,1]]; const arr2 = [[0,1,3,4], [0,1], [0], [0,1]];
첫 번째 예제는 2개의 배열, 두 번째 예제는 4개의 배열을 다룹니다. 이렇게 유동적인 입력을 처리하려면 재귀 호출을 기반으로 한 범용 함수가 필요합니다.
구현 코드
재귀 헬퍼 함수를 사용하면 임의의 개수를 가진 배열에서도 모든 조합을 손쉽게 생성할 수 있습니다.
const arr = [
[0,1],
[0,1,2,3],
[0,1,2]
]
const combineAll = (array) => {
const res = [];
let max = array.length - 1;
const helper = (arr, i) => {
for (let j = 0, l = array[i].length; j < l; j++) {
let copy = arr.slice(0);
copy.push(array[i][j]);
if (i == max)
res.push(copy);
else
helper(copy, i + 1);
}
};
helper([], 0);
return res;
};
console.log(combineAll(arr));동작 방식 살펴보기
코드의 핵심 로직은 다음과 같이 정리할 수 있습니다.
- helper 함수: 현재 처리 중인 배열의 인덱스(i)를 받아 해당 배열의 모든 요소를 순회합니다.
- copy 배열: arr.slice(0)으로 기존 배열을 복사한 뒤 현재 요소를 추가합니다. 이렇게 하면 각 분기가 독립적인 경로를 유지할 수 있습니다.
- 종료 조건: 마지막 배열(max)까지 처리했다면 완성된 조합을 결과 배열(res)에 저장하고, 그렇지 않으면 다음 배열을 대상으로 재귀 호출을 진행합니다.
즉, 첫 번째 배열부터 순서대로 깊이 우선 탐색(DFS)과 유사한 방식으로 모든 경우의 수를 탐색하게 됩니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 0, 2 ], [ 0, 1, 0 ], [ 0, 1, 1 ], [ 0, 1, 2 ], [ 0, 2, 0 ], [ 0, 2, 1 ], [ 0, 2, 2 ], [ 0, 3, 0 ], [ 0, 3, 1 ], [ 0, 3, 2 ], [ 1, 0, 0 ], [ 1, 0, 1 ], [ 1, 0, 2 ], [ 1, 1, 0 ], [ 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 2, 0 ], [ 1, 2, 1 ], [ 1, 2, 2 ], [ 1, 3, 0 ], [ 1, 3, 1 ], [ 1, 3, 2 ] ]
총 2 × 4 × 3 = 24개의 조합이 생성된 것을 확인할 수 있습니다. 일반적으로 결과 조합의 개수는 각 배열 길이의 곱과 같으므로, 입력 배열이 커질 경우 조합 수가 기하급수적으로 늘어난다는 점을 염두에 두고 사용하는 것이 좋습니다.