자바스크립트 배열에서 모든 항목의 조합을 구하는 알고리즘

문자열 리터럴로 이루어진 배열을 인수로 받아, 배열에 포함된 문자열들의 가능한 모든 조합을 생성하고 반환하는 자바스크립트 함수를 작성해야 합니다.

문제 예시

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

const arr = ['a', 'b', 'c', 'd'];

이 경우 기대하는 출력 결과는 다음과 같습니다.

const output = ["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"];

접근 방식

이 문제는 재귀(Recursion)를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 각 단계에서 현재까지 만들어진 부분 조합(sub)에 새로운 요소를 하나씩 추가합니다.
• 중복된 조합이 생기지 않도록, 재귀 호출은 항상 현재 선택한 요소의 다음 인덱스부터 진행합니다.
• 요소를 추가할 때마다 해당 조합을 결과 배열에 저장하고, 동시에 더 긴 조합을 만들기 위해 재귀 호출을 이어갑니다.

구현 코드

const getCombinations = (arr = []) => {
    const combine = (sub, ind) => {
        let result = []
        let i, l, p;
        for (i = ind, l = arr.length; i < l; i++) {
            p = sub.slice(0);
            p.push(arr[i]);
            result = result.concat(combine(p, i + 1));
            result.push(p.join(''));
        };
        return result;
    }
    return combine([], 0);
};
console.log(getCombinations(["a", "b", "c", "d"]));

코드 설명

• combine(sub, ind): 현재까지의 부분 조합 sub와 탐색을 시작할 인덱스 ind를 받습니다.
• sub.slice(0): 기존 배열을 복사하여 원본 조합이 변경되지 않도록 합니다.
• p.join(''): 배열 형태의 조합을 하나의 문자열로 변환합니다.

출력 결과

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

[
    'abcd', 'abc', 'abd',
    'ab', 'acd', 'ac',
    'ad', 'a', 'bcd',
    'bc', 'bd', 'b',
    'cd', 'c', 'd'
]

배열의 순서는 재귀 호출 구조에 따라 달라질 수 있지만, n개의 요소에서 만들 수 있는 모든 조합(2ⁿ − 1개)이 빠짐없이 포함됩니다. 위 예시에서는 4개의 요소로부터 15개의 조합이 정확히 생성된 것을 확인할 수 있습니다.