[Algorithm] 멱집합(PowerSet)

멱집합은 어떤 집합의 모든 부분 집합의 집합이다.
input으로 문자열을 받았을 때, 해당 문자열의 멱집합을 구하는 로직을 공부해본다.
토이 시간에 시간 내에 풀어내지 못해서 아쉬웠던 문제였다!

[주의 사항]

1. 리턴값은 알파벳, 사전식 순서로 정렬되어야 한다.
2. 집합은 중복된 원소를 허용하지 않는다.
3. 빈 문자열을 포함한다.

  // 처음에는 트리처럼 나열해 부분집합을 구상해봤다.
  // 그러나 애초에 문자열의 중복을 제거하기 때문에 해당 요소를 포함한다/안한다로 재귀 스택을 쌓아가면 된다.

  //           a(o)                    b(o)                    c(o)
  //    a      b(o)   c(o)      a      b      c(o)      a      b      c
  //  a b c   a b c  a b c    a b c  a b c  a b c     a b c  a b c  a b c
  //  x x x   x x o  x x x    x x x  x x x  x x x     x x x  x x x  x x x

// PowerSet
function powerSet(str) {
  // 문자 정렬
  let strArr = str.split('').sort();
  // 중복 제거
  let uniqueStrArr = strArr.filter((item, index) => strArr.indexOf(item) === index);
  
  let subSets = [];
  function pickOrNot(i, subset) {
    // 위 구조처럼 트리의 DFS처럼 재귀를 이용
    
    // 탈출
    if (i가 strArr의 끝에 도달할 때) {
      // subSets에 현재까지 구성된 subset을 저장 
      return;
    }
    
    // 재귀
    // i번째 문자를 포함하지 않는 경우
    pickOrNot(i + 1, subset);
    // i번째 문자를 포함하는 경우
    pickOrNot(i + 1, subset + strArr[i]);
  };
  
  pickOrNot(0, '');
  
  return subSets.sort();
};