주어진 문자열의 부분집합을 사전식으로 정렬된 배열로 표현하시오.

작성 코드

(JAVA 언어로 작성된 코드 검색하여 참조. 재귀함수의 호출 스택 특성을 사용한 것으로, 아래의 그림을 참고함.)

const powerSet = function (str) {
  // TODO: 여기에 코드를 작성합니다.
  /*
  일단은 만들어 놓고, sort() 하면 알아서 정렬되네. 그걸 바로 리턴하면 됨.
  */

  //str에서 중복된 문자는 제거하여 새 str을 만든다
  let strArr = str.split('');
  let obj = {};
  strArr.forEach(el => {
    if(obj[el] === undefined){
      obj[el] = 1;
    }
  })
  strArr = Object.keys(obj).sort() // 중복된 문자가 제거된 문자 배열. 또, 정렬 미리 해줘야 편함ㅎㅎ

  //결과를 저장할 배열 만들기
  const result = []; 

  //부분집합 만들어서 result에 push한다. 단, 같은 부분집합이 있는 경우에는 push하지 않는다. 
  //1글자: str 순회하며 str[i]를 넣는다. 단 겹치지 않는 경우만.
  //2글자: jump의 경우 다음과 같다. 

  /*
  jump에 대해서: 
  j 포함 안포함
  u 포함 안포함
  m 포함 안포함
  p 포함 안포함
  이진트리의 dfs 활용
  */
  const checked = new Array(strArr.length).fill(false); // true일때만 부분집합의 원소로 사용하겠다는 의미. 

  function dfs(index){
    if(index === strArr.length){ //base case : 인덱스가 배열의 길이와 같을 경우에는 트리의 가장 마지막까지 다 봤단 소리니까 true 여부 따라서 부분집합 만든다. 
      let str = '';
      for(let i = 0; i < strArr.length; i++){
        if(checked[i]) str += strArr[i]
      }
      result.push(str);
//솔직히 이 아래의 코드 적기는 혼자서 못할거같다. 
// 그림 그리면 코드 이해 되는데 반대로는 호출스택을 어떻게 연관지어야 할지 모르겠다. 
//01, 0, 1, '' 이런 순서로 작동함. 
    
}else{ //recursive. 트리의 끝까지 내려가면서 true 여부 체크한다. 어떻게??????
      checked[index] = true; //[true, false] //[true,true]
      dfs(index + 1); //dfs(1) //dfs(2) - ab
      checked[index] = false; //dfs(2) 에서 ab 넣고 나간 후 dfs(1) 재개 [true,false] a
      dfs(index + 1);
    }
  }
  dfs(0);

  //정렬한다
  result.sort();

  //결과 리턴한다
  return result;
};

재귀적 사고를 이용한 좀 더 쉬운 방법

근거

문제를 좀 더 작은 문제로 나눠보면, 배열의 원소 1개와 나머지 배열로 나눌 수 있다.

원소가 1개인 배열은 부분집합을 바로 쉽게 구할 수 있으니까. 이것을 base case로 두고, 나머지 배열은 재귀함수한테 처리해달라고 맡기면 되는 것이다!

예를 들어 “BC” 문자열의 부분집합을 구하려면, “B”와 “C”로 나눈다.

그런 다음, “B”의 부분집합은 [’’, “B”] 임을 쉽게 구할 수 있고, “C”의 부분집합은 “B”의 부분집합과, “B”의 부분집합을 순회하면서 “C”를 붙인 집합을 합해서 구할 수 있다.

이 과정을 아래 블로그에서 잘 설명하고 있었다.

//좀 더 쉬운 접근 방법!!:)
const powerSet = function (str){
  //주어진 문자열을 배열로 전환 후, 중복 문자열을 제거한다.
  let arr = Array.from(str).sort();
  arr = arr.reduce((acc,cur) => {
    if(acc[acc.length - 1] === cur){
      return acc;
    }else{
      return acc.concat(cur);
    }
  },[])

  function recurse(arr){
    if(arr.length === 1){
      return ["", arr[0]];
    }else{
      return recurse(arr.slice(1)).concat(recurse(arr.slice(1)).map(el => arr[0].concat(el)));
    }
  }

  return recurse(arr).sort();
}