[JS][코플릿]Immersive Toy Problem-11_powerSet[DFS]

문제

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

입력

인자 1 : str

• string 타입의 공백이 없는 알파벳 소문자 문자열

출력

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

주의사항

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

입출력 예시

let output1 = powerSet('abc');
console.log(output1); // ['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']

let output2 = powerSet('jjump');
console.log(output2); // ['', 'j', 'jm', 'jmp', 'jmpu', 'jmu', 'jp', 'jpu', 'ju', 'm', 'mp', 'mpu', 'mu', 'p', 'pu', 'u']

👻하

 

킹규명님의노션풀이

onst 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);
      }
    });
    console.log(deduplicated);
    //------------------------------------
    let subSets = [];
    const pickOrNot = (idx, subset) => {
      console.log(idx, subset);
      if (idx === deduplicated.length) {
        return subSets.push(subset);
      }
	//------------------------------------
      console.log("있다->", idx, subset);
      pickOrNot(idx + 1, subset + deduplicated[idx]);
      console.log(subSets);
      console.log("없다->", idx, subset);
      pickOrNot(idx + 1, subset);
      console.log(subSets);
    };
    //------------------------------------
    pickOrNot(0, "");

    return subSets.sort();
  };
  let output2 = powerSet("jjump");
  // console.log(output2);

jjump인 경우

중복제거하고 jump

정렬해서 jmpu

4층까지 내려갔다가 아니면 뒤로 백.

+1 부분에서 return되면 뒤로 백이 되는거시다...

이렇게생긴거 트리2개있다고 생각하라! -j인경우

👀

 

 

---

 

https://hianna.tistory.com/422

[Javascript] 배열 중복 제거하는 3가지 방법

(forEach()와 filter()는 적용이 안된다....왜지?)

 

배열중복제거부분을 찾아보다가 new Set()를 알게되어 적용해보았다.

const powerSet = function (str) {
  const set = new Set(str); //중복제거된 객체반환
  const deduplicated = [...set].sort(); //배열로만들어서 정렬
  
  const subSets=[];
  const pickOrNot = (idx, subset) => {
    if(idx === deduplicated.length){
      return subSets.push(subset);
    }
    pickOrNot(idx+1, subset+deduplicated[idx]);
    pickOrNot(idx+1, subset);
  }
  pickOrNot(0,'');
  return subSets.sort();
};