[Algorithm] Powerset 알고리즘 뽀개기

 

 

어제 Powerset 알고리즘 공부를 하다 결국 침대에 누워 서럽게 울다 지쳐 잠이 들었다...

 

 

나만 이해가 안되는 건가..?

 

 

하지만 정신을 차렸으니 다시 한 번 꼼꼼이 파헤처 보도록 하자. 

 

일단은 Poserset에 대한 기본적인 이해부터 해보도록 해보겠다. 

 

Powerset = 멱집합

 

The power set is a set which includes all the subsets including the empty set and the original set itself.

 

멱집합이란 빈집합부터 원래 요소를 모두 포함한 집합까지의 모든 하위 집합을 말한다. 

 

즉 {1, 2, 3}의 멱집합은 다음과 같다: {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

 

 

Powerset Algorithm

 

우선은 구글에서 돌아다니는 Powerset 알고리즘(Javascript)은 아래와 같다. 

 

const getSubsets = function (arr) {
  let flag = new Array(arr.length).fill(false);
  const subSets = [];

  const subSet = function DFS (depth) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (depth === arr.length) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[depth] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(depth + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[depth] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(depth + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

  subSet(0); // depth 0 부터 시작
  return subSets;
}
const example = [1,2,3];
const result = getSubsets(example);

 

심호흡 한 번 하고 부분부분 뜯어서 살펴보자. 

 

---

Step 1

result 상수에는 getSubset([1,2,3])을 계산한 결과가 담기게 된다. 

const example = [1,2,3];
const result = getSubsets(example);

 

Step 2

아래과 같은 이유로, flag 변수에는 [false, false, false] 배열이 담기게 된다.

const getSubsets = function ([1,2,3]) {
let flag = new Array([1,2,3].length).fill(false);

 

Step 3

subset 함수의 파라미터로 0을 전달해 연산을 시작한다.

subSet(0); // depth 0 부터 시작

 

Step 4

0의 인자가 전달되면 subSet 함수는 아래와 같이 연산하게 된다. 

 

재귀함수가 호출될 예정이므로 아래의 코드를 Tier 1이라 부르겠다. 

 

<Tier 1>

const subSet = function DFS (0) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (0 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[0] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(0 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[0] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(0 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건은 맞지 않으므로 Pass

flag[0] = true; // 해당 depth의 flag true = 트리의 왼쪽

위의 코드로 인해 변수 Tier 1 - flag의 상태는 아래와 같이 변경

[true, false, false]

 

subSet(1)의 호출로 재귀함수 실행

 

Step 5

재귀함수가 호출되었다. Tier 2의 함수는 아래와 같이 연산된다.

<Tier 2>

const subSet = function DFS (1) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (1 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[1] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(1 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[1] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(1 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건은 맞지 않으므로 Pass

flag[1] = true; // 해당 depth의 flag true = 트리의 왼쪽

위의 코드로 인해 변수 Tier 2 - flag의 상태는 아래와 같이 변경

[true, true, false]

 

subSet(2)의 호출로 재귀함수 실행

 

Step 6

재귀함수가 호출되었다. Tier 3의 함수는 아래와 같이 연산된다.

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건은 맞지 않으므로 Pass

flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[true, true, true]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 7

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [true, true, true]

subSets = [[1,2,3]]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다. 

 

Step 8

Tier4가 종료되었기 때문에 이제 Tier3에서 나머지 실행되지 못한 코드를 실행한다. 

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

아직 실행되지 못한 나머지 코드들

flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[true, true, false]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 9

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [true, true, false]

subSets = [[1,2,3], [1,2]]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다.

 

Step 10

더 이상 Tier3에서도 실행될 코드가 남아있지 않다. 

따라서 Tier2로 넘어가게 된다. 

<Tier 2>

const subSet = function DFS (1) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (1 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[1] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(1 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[1] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(1 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

아직 실행되지 못한 나머지 코드들

flag[1] = false; // 해당 depth의 flag false = 트리의 오른쪽
subSet(1 + 1); // 트리의 오른쪽에 대해 재귀 호출

위의 코드로 인해 변수 Tier 2 - flag의 상태는 아래와 같이 변경

[true, false, false]

 

subSet(2)의 호출로 재귀함수 실행

 

Step 11

재귀함수가 호출되었다. Tier 3의 함수는 아래와 같이 연산된다.

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건은 맞지 않으므로 Pass

flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[true, false, true]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 12

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [true, false, true]

subSets = [[1,2,3], [1,2], [1,3]]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다.

 

Step 13

Tier4가 종료되었기 때문에 이제 Tier3에서 나머지 실행되지 못한 코드를 실행한다. 

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

아직 실행되지 못한 나머지 코드들

flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[true, false, false]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 14

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [true, false, false]

subSets = [[1,2,3], [1,2], [1,3], [1]]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다.

 

Step 15

더 이상 Tier3에서도 실행될 코드가 남아있지 않다. 

따라서 Tier2로 넘어가게 된다. 

 

더 이상 Tier2에서도 실행될 코드가 남아있지 않다. 

따라서 Tier1으로 넘어가게 된다. 

 

<Tier 1>

const subSet = function DFS (0) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (0 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[0] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(0 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[0] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(0 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

 

아직 실행되지 못한 나머지 코드들

flag[0] = false; // 해당 depth의 flag false = 트리의 오른쪽
subSet(0 + 1); // 트리의 오른쪽에 대해 재귀 호출

위의 코드로 인해 변수 Tier 1 - flag의 상태는 아래와 같이 변경

[false, false, false]

 

subSet(1)의 호출로 재귀함수 실행

 

Step 16

 

재귀함수가 호출되었다. Tier 2의 함수는 아래와 같이 연산된다.

<Tier 2>

const subSet = function DFS (1) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (1 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[1] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(1 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[1] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(1 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건은 맞지 않으므로 Pass

flag[1] = true; // 해당 depth의 flag true = 트리의 왼쪽

위의 코드로 인해 변수 Tier 2 - flag의 상태는 아래와 같이 변경

[false, true, false]

 

subSet(2)의 호출로 재귀함수 실행

 

Step 17

재귀함수가 호출되었다. Tier 3의 함수는 아래와 같이 연산된다.

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건은 맞지 않으므로 Pass

flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[false, true, true]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 18

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [false, true, true]

subSets = [[1,2,3], [1,2], [1,3], [1], [2,3]]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다. 

 

Step 19

Tier4가 종료되었기 때문에 이제 Tier3에서 나머지 실행되지 못한 코드를 실행한다. 

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

아직 실행되지 못한 나머지 코드들

flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[false, true, false]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 20

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [false, true, false]

subSets = [[1,2,3], [1,2], [1,3], [1], [2,3], [2]]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다. 

 

Step 21

더 이상 Tier3에서도 실행될 코드가 남아있지 않다. 

따라서 Tier2로 넘어가게 된다. 

<Tier 2>

const subSet = function DFS (1) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (1 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[1] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(1 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[1] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(1 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

아직 실행되지 못한 나머지 코드들

flag[1] = false; // 해당 depth의 flag false = 트리의 오른쪽
subSet(1 + 1); // 트리의 오른쪽에 대해 재귀 호출

위의 코드로 인해 변수 Tier 2 - flag의 상태는 아래와 같이 변경

[false, false, false]

 

subSet(2)의 호출로 재귀함수 실행

 

Step 22

재귀함수가 호출되었다. Tier 3의 함수는 아래와 같이 연산된다.

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건은 맞지 않으므로 Pass

flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[false, false, true]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 23

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [false, false, true]

subSets = [[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3]]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다. 

 

Step 24

Tier4가 종료되었기 때문에 이제 Tier3에서 나머지 실행되지 못한 코드를 실행한다. 

<Tier 3>

const subSet = function DFS (2) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (2 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[2] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(2 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

아직 실행되지 못한 나머지 코드들

flag[2] = false; // 해당 depth의 flag false = 트리의 오른쪽
subSet(2 + 1); // 트리의 오른쪽에 대해 재귀 호출

위의 코드로 인해 변수 Tier 3 - flag의 상태는 아래와 같이 변경

[false, false, flase]

 

subSet(3)의 호출로 재귀함수 실행

 

Step 25

재귀함수가 호출되었다. Tier 4의 함수는 아래와 같이 연산된다.

<Tier 4>

const subSet = function DFS (3) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (3 === 3) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[3] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(3 + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[3] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(3 + 1); // 트리의 오른쪽에 대해 재귀 호출
  }

if 문의 조건이 맞으므로 if 문이 실행된다.

const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
subSets.push(subSet); // 부분집합들을 담는 배열에 push

위의 코드로 인해 flag 변수가 true 인 인자들이 subSets에 push 되므로, 

subSets 변수는 아래와 같이 변한다. 

 

flag = [false, false, flase]

subSets = [[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []]

 

if문의 마지막에 return을 만나게 되며 Tier 4는 종료된다. 

 

Step 26

 

더 이상 Tier3에서도 실행될 코드가 남아있지 않다.

따라서 Tier2로 넘어가게 된다. 

 

더 이상 Tier2에서도 실행될 코드가 남아있지 않다. 

따라서 Tier1으로 넘어가게 된다. 

 

더 이상 Tier1에서도 실행될 코드가 남아있지 않다.

따라서 함수 subset(0)은 종료된다.

 

---

 

이상으로 정말 무식하게 알고리즘이 작동하는 방식을 살펴보았다. 

 

하나하나 따라가다 보니 왜 이 알고리즘이 멱집합을 반환하는지 이해는 된다. 

 

하지만 이 코드를 내가 진짜 머리로 생각해서 작성할 수 있을까? 는 사실... 아직은 자신이 없다. 

 

으으