201228 - 알고리즘

[토이11]

powerSet

문제
하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다.

입력
인자 1 : str
string 타입의 공백이 없는 알파벳 소문자 문자열

출력
배열(arr)을 리턴해야 합니다.
arr[i]는 각 부분집합의 원소로 구성된 문자열

주의사항
arr[i]는 각 부분집합을 구성하는 원소를 연결한 문자열입니다.
arr[i]는 알파벳 순서로 정렬되어야 합니다.
집합은 중복된 원소를 허용하지 않습니다.
부분집합은 빈 문자열을 포함합니다.
arr은 사전식 순서(lexical order)로 정렬되어야 합니다.

시도한 오답

///어떻게 풀어야할지 모르겠는데...
// 순열
// dfs

const powerSet = function (str) {

  arr = [str];
  let dd = new Array(arr.length).fill(false);
  let results = [];

  let result = function dfs (depth) {
    if (depth === arr.length) {
      let result = arr.filter((value, index) => dd[index]);
      results.push(result);
      return;
    }
    dd[depth] = true
    result(depth+1)
    dd[depth] = false
    result(depth+1)
  }
  result(0)
  return results.sort()
};

ref

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();
};

// 음 잘 모르겠담...

멱집합

멱집합에 대한 자세한 설명은 👉️ 여기를 참고

출처 : https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%EB%A9%B1%EC%A7%91%ED%95%A9-powerset-%EB%A6%AC%ED%84%B4%ED%95%98%EB%8A%94-%ED%95%A8%EC%88%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-f1cce8cc3268 💚️