1. 멱집합

---

• 멱집합(power set)은 해당 집합의 모든 부분집합을 말한다.

{1, 2, 3}

// 아래 8개의 부분 집합은 집합 {1, 2, 3}의 멱집합이다.
{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

1) 모든 부분집합 나열 방법

• 모든 부분집합을 나열하는 방법은 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지에 따라 단계를 나누는 기준을 결정한다.

• 원소가 있는지, 없는지 2가지의 경우를 고려하기 때문에 집합의 요소가 n개일 때 모든 부분집합의 개수는 2^n개다.

• Step A: 1을 제외한 {2, 3}의 부분집합을 나열한다.

  • Step B: 2를 제외한 {3}의 부분집합을 나열한다.
    • Step C: 3을 제외한 {}의 부분집합을 나열한다. → {}
    • Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열한다. → {3}
  • Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열한다.
    • Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면, {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열한다. → {2}, {2, 3}

• Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한다.

  • Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면, {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한다.
    • Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열한다. → {1}, {1, 3}
    • Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열한다. → {1, 2}, {1, 2, 3}

function powerSet(arr) {
    const result = [];

    function recursion(subset, start) {
        result.push(subset);
        for (let i = start; i < arr.length; i++) {
            // 1. spread 연산자로 합치는 방법
            recursion([...subset, arr[i]], i + 1);
            // 2. concat 메서드로 합치는 방법
            recursion(subset.concat(arr[i]), i + 1);
        }
    }
    recursion([], 0);
    return result;
}

poserSet(['a', 'b', 'c']);
// [
//     [],
//     ['a'],
//     ['a', 'b'],
//     ['a', 'b', 'c'],
//     ['a', 'c'],
//     ['b'],
//     ['b', 'c'],
//     ['c']
// ]