011. powerSet

powerSet
주어진 문자열의 'power set'으로 이루어진 배열을 return하는 함수를 작성하세요.
power set이란? 비어있는 집합을 포함한 모든 부분집합(subset)의 모음.
예시:
powerSet("abc")
// [ '' , 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc' ]
참고:
모든 부분집합의 문자들은 알파벳 순서로 정렬되어야 합니다.
같은 문자로 이루어진 부분집합은 순서와 무관하게 하나로 인식합니다. ('ab'와 'ba'는 같습니다.)
예시2 :
powerSet("jump")
// ["", "j", "ju", "jm", "jp", "jmu", "jmp", "jpu", "jmpu", "u", "m", "p", "mu", "mp", "pu", "mpu"]

답안

const powerSet = function (str) {
  
//결과가 될 값은 부분집합 문자열들이 모여있는 배열이다.
//문자열에서 각 위치마다 값을 없애는 함수가 필요하다
//중간에 이 값이 이전에 들어왔는지 판별해주는 key:value모양의 필터해주는 부분이 필요하다.
// 중복되는 값은 미리 제거한다.

//set은 결과값들을 넣을 배열, hash는 결과값 후보들이 중복되는경우 걸러지는 부분이다.
  var set = [];
  var hash = {};
  if(!str) str = '';
  str = str.split('').sort();

  
  // 위에서 sort()를 해주었기 때문에 같은 알파벳은 인접해있다.
  // 반복분으로 중복되는값이 이어져있는경우 뒤에있는 중복값을 지운후 
  // 다시 앞의 중복값으로 돌아와서 반복문을 이어간다.
  for(var i = 1; i < str.length; i++){
    if(str[i - 1] === str[i]){
      str.splice(i, 1);
      i--;
    }
  }

// 중복되는 값이 없는 정렬된 알파벳들의 배열을 다시 문자열로 만든다.
  function recurse(strSet){
    var joined = strSet.join('');

    //결과값에 넣기 전 이전에 이미 들어왔었는지 확인한다.
    if(hash[joined]) return;
    //없다면 해당값을 key값으로, true를 밸류로 넣는다.
    hash[joined] = true;
    //결과값에도 추가한다.
    set.push(joined);

    // 아래있는 반복문에 의해 한자리씩 계속 빠지는 재귀가 생기는데 
    // 1자리인경우에 재귀를 종료한다.
    if(strSet.length === 1) return;

    // 이부분은 직접 콘솔에 적용해가면서 확인했다.
    // 문자열의 각 자리가 한번씩 제거된다.
    for(var i = 0; i < strSet.length; i++) {
      var subSet = strSet.slice(0, i).concat(strSet.slice(i + 1));
      recurse(subSet);
    }
  }
  recurse(str);
  // 마지막으로 빈문자열도 추가해준다.
  set.push(''); 
  return set;
};