[Algorithm] _powerSet

문제

하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다.

입력

인자 1 : str

string 타입의 공백이 없는 알파벳 소문자 문자열

출력

배열(arr)을 리턴해야 합니다.
arr[i]는 각 부분집합의 원소로 구성된 문자열

입출력 예시

let output1 = powerSet('abc');
console.log(output1); // ['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']

let output2 = powerSet('jjump');
console.log(output2); // ['', 'j', 'jm', 'jmp', 'jmpu', 'jmu', 'jp', 'jpu', 'ju', 'm', 'mp', 'mpu',

재귀로 호출되는 콜스택이 너무 많아서 이해하는데 힘든 문제였다.. 이 문제를 이해하기 위해서는 멱집합의 개념을 알아야하는데, 멱집합이란 주어진 집합의 모든 부분집합으로 구성된 집합이다.

모든 경우의 수를 구하기 위해, 재귀를 활용해야한다. 그림을 그려보자면, Binary Tree와 같은 구조인데 문자열의 요소들을 검사하면서, 해당 문자를 포함하지 않는다면 다음 문자로 넘어가고 (빨간줄) 포함한다면 문자를 조합해주는 식으로 (파란줄) 모든 요소를 검사하면 멱집합을 구할 수 있다.

이 구조를 코드로 표현한다면 아래와 같다.

const powerSet = function (str) {
    // 문자 배열 알파벳 순 정렬
    const sorted = str.split("").sort();
    // 중복 요소 제거
    const uniqueEle = sorted.reduce((acc, cur) => {
        if (acc[acc.length - 1] === cur) {
            return acc;
        } else {
            return acc + cur;
        }
    })
    // 문자 조합 찾는 재귀함수
    const subsets = [];
    const findCombi = (subset, idx) => {
        // base case : 모든 요소를 검사했을 경우
        if (idx === uniqueEle.length) {
            return subsets.push(subset);
        }
        // recur case : 모든 idx를 검사할 때까지 아래를 반복
        // idx의 요소를 포함하지 않을 경우, 그냥 다음 idx로 넘어감
        findCombi(subset, idx + 1); // 그림에서 빨간 줄에 해당
        // idx의 요소를 포함할 경우, 해당 idx의 요소를 더해줌
        findCombi(subset + uniqueEle[idx], idx + 1); // 그림에서 파란줄에 해당
    }
    // 재귀함수 실행
    findCombi("", 0)
    // 결과 알파벳 순서 정렬
    return subsets.sort();
};