멱집합

powerSet

문제

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

입력

인자 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']

 

 

멱집합 

주어진 모든 집합의 부분 집합을 구하는 알고리즘 문제

 

DFS트리를 통하여 알아볼수있다.

Depth가 배열의 길이보다 많아졌을때 출력! 

요소를 선택했는지 안했는지 확인해줄 것이 필요하다 <= 체크리스트

 

DFS를 통하여 구현하는 방법

 

1. 선택했는지 선택하지 않았는지 확인해줄 check배열을 만든다.
   • arr배열에서 check배열과 같은 인덱스에 있는 요소만 부분집합으로 만들어 줄 것이다.
2. dfs 함수

2-1. (재귀 종료조건) depth가 check.length와 같아지면 arr에서 check가 1인 인덱스의 값만 매핑해서 powerSetArr에 push해준다.

2-2.

• 현재 depth(index)가 포함된 경우 : check배열에 1로 바꾸어주고 dfs(depth+1)로 또 타고들어간다.
• 현재 depth(index)가 포함되지 않은 경우 : check배열에서 0으로 다시 바꿔주고 dfs(depth+1)로 들어간다.

 

 

다른 풀이방식

const powerSet = function (str) {
  // TODO: 여기에 코드를 작성합니다.
  let arr = str.split('').sort()
  let result = [''];

  let aux = (target,result) =>{
    let copy = result.slice();
    for(let i=0; i<copy.length; i++){
      copy[i] = copy[i] + target
      result.push(copy[i])
    }
     return result;
  }

  for(let i=0; i<arr.length; i++){
    if(!result.includes(arr[i])){
      aux(arr[i],result)
    }
  }
  return result.sort()
};