JavaScript로 문자열의 모든 가능한 조합 생성하기

문자열을 인수로 하나만 받아서, 해당 문자열에서 만들 수 있는 모든 가능한 조합을 배열 형태로 반환하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어 'Delhi'라는 문자열이 입력되면, 각 문자(D, e, l, h, i)를 포함하거나 포함하지 않는 모든 경우의 수를 조합해 결과 배열을 생성해야 합니다.

접근 방법

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.

• 1단계: 문자열을 개별 문자로 분리해 배열에 저장합니다.
• 2단계: 길이가 n인 문자열은 최대 2ⁿ개의 조합을 가질 수 있으므로, 비트 연산(&)을 활용해 각 문자의 포함 여부를 판단하고 모든 조합을 생성합니다.

코드 구현

다음은 전체 구현 코드입니다.

const str = 'Delhi';
const allCombinations = (str1 = '') => {
    const arr = [];
    for (let x = 0, y = 1; x < str1.length; x++, y++) {
        arr[x] = str1.substring(x, y);
    };
    const combination = [];
    let temp = "";
    let len = Math.pow(2, arr.length);
    for (let i = 0; i < len; i++) {
        temp = "";
        for (let j = 0; j < arr.length; j++) {
            if ((i & Math.pow(2, j))) {
                temp += arr[j];
            }
        };
        if (temp !== "") {
            combination.push(temp);
        }
    }
    return combination;
};
console.log(allCombinations(str));

코드 동작 원리

코드가 어떻게 작동하는지 단계별로 살펴보겠습니다.

1. 첫 번째 반복문에서 substring(x, y)를 이용해 문자열을 한 글자씩 잘라 배열 arr에 저장합니다. 'Delhi'의 경우 ['D', 'e', 'l', 'h', 'i']가 됩니다.
2. 길이가 5인 문자열의 조합 수는 2⁵ = 32개입니다. 변수 len에 이 값이 저장됩니다.
3. 외부 반복문의 i(0부터 31까지)를 하나의 비트마스크처럼 활용합니다. 내부 반복문에서 i & Math.pow(2, j) 연산으로 i의 j번째 비트가 1인지 검사합니다.
4. 비트가 1이면 해당 위치의 문자를 temp에 이어 붙이고, 최종적으로 빈 문자열이 아닌 값만 결과 배열에 추가합니다.

즉, i의 이진수 표현이 각 문자의 포함 여부를 나타내므로, 0부터 2ⁿ-1까지 순회하는 것만으로 모든 부분집합 조합을 빠짐없이 생성할 수 있습니다.

출력 결과

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

[
    'D', 'e', 'De', 'l',
    'Dl', 'el', 'Del', 'h',
    'Dh', 'eh', 'Deh', 'lh',
    'Dlh', 'elh', 'Delh', 'i',
    'Di', 'ei', 'Dei', 'li',
    'Dli', 'eli', 'Deli', 'hi',
    'Dhi', 'ehi', 'Dehi', 'lhi',
    'Dlhi', 'elhi', 'Delhi'
]

빈 문자열('')은 제외된 31개의 조합이 모두 출력되는 것을 확인할 수 있습니다. 이 접근 방식은 시간 복잡도가 O(n × 2ⁿ)이므로, 문자열 길이가 너무 길어지지 않는 경우에 효율적으로 동작합니다.