PowerSet 알고리즘

const powerSet = function (str) {
  // 정렬
  const sorted = str.split('').sort();
  //각자 문자로 분리하여 알파벳 정렬 후 배열에 저장한다.
  // 중복 제거
  const deduplicated = sorted.reduce((acc, item) => {
    //첫번째는 이전까지의 계산 결과를 누적하는 변수
    //두번째는 배열의 요소 하나
    if (acc[acc.length - 1] === item) {
      return acc;
    } else {
      return acc.concat(item);
    }
  });

  let subSets = [];
  const pickOrNot = (idx, subset) => {
    // base case
    if (idx === deduplicated.length) {
      // 마지막 문자까지 검토한 경우
      subSets.push(subset);
      return;
    }

    // recursive case
    // idx번째 문자가 포함되지 않는 경우
    pickOrNot(idx + 1, subset);

    // idx번째 문자가 포함되는 경우
    pickOrNot(idx + 1, subset + deduplicated[idx]);
  }; 

  pickOrNot(0, '');

  return subSets.sort();
};

subSets 변수는 부분집합을 저장하는 배열이다.

pickOrNot 함수는 재귀적으로 호출되는데

idx는 현재 검토할 문자의 인덱스를 나타내고,

subset은 이전까지 선택한 문자열의 부분집합을 나타낸다.

pickOrNot 함수에서는 두 가지 경우를 모두 검토한다.

첫번째 경우는 idx번째 문자를 선택하지 않는 경우: pickOrNot(idx + 1, subset)를 호출합니다.

두번째 경우는 dx번째 문자를 선택하는 경우: pickOrNot(idx + 1, subset + deduplicated[idx])를 호출합니다. 이때 subset 문자열에 deduplicated[idx]를 추가한다.

idx가 문자열의 마지막 인덱스인 경우(base case), subSets 배열에 subset을 추가한다.

이러한 방식으로 모든 부분집합을 찾아 subSets 배열에 저장한다.

ex) let str = 'abc'

중복을 제거하고 알파벳순으로 정렬한 deduplicated 배열은 ['a', 'b', 'c']가 됩니다.

 

idx번째 문자가 포함되지 않는 경우
처음에는 pickOrNot(0, '') 함수를 호출합니다. 이때 idx는 0이고, subset은 빈 문자열('')이다.

pickOrNot(1,"")
pickOrNot(2,"")
pickOrNot(3,"")로 

idx는 deduplicated의 길이와 같으므로 subset는 빈배열이 추가된다.

 

idx번째 문자가 포함된 경우

pickOrNot(1,"" + a)

pickOrNot(2,""+ a)

pickOrNot(3,""+ a)

 

subset = ["" , 'a"]

 

 

 

Regenerate response