[JS]모든 부분 집합(멱집합) 구하기

Kyle·2020년 12월 26일

JavaScript 멱집합

algorithm & Data structure

목록 보기

7/8

멱집합

과정은 비슷하지만 2가지 버전으로 구현했다.

멱집합이란 주어진 집합의 모든 부분집합을 구하는 것이다.

여기서 모든 부분집합이라는 것은 무엇을 뜻하는 것일까?

ex) [1,2,3] 이라는 배열의 모든 부분집합을 구하여라

[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

위와 같이 모든 [1,2,3]에 속해 있는 부분집합들 전부를 통칭해 멱집합(모든 부분집합)이라 한다.

이제 javascript를 이용해서 구현해보자.

설계

각요소가 선택될지, 선택되지 않을지를 결정하는 dfs트리를 만들어서 해결해보았다.

예시로 [1,2,3] 배열에서 생각해보자.

위의 그림과 같이 각각의 숫자를 선택할 경우 선택하지 않을 경우를 나눠준다. Depth가 배열의 길이보다 많아졌을 때 출력해주면된다.

각각의 요소를 선택했는지 안했는지를 확인해줄 check배열이 따로 있어야 한다. 초기값을 0으로 설정했고 선택한다면 1로 바꿔준다.

코드 흐름

선택했는지 선택하지 않았는지 확인해줄 check배열을 만든다.
- arr배열에서 check배열과 같은 인덱스에 있는 요소만 부분집합으로 만들어 줄 것이다.
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)로 들어간다.

code

function powerSet(arr) {
  //check표시 해줄 배열
  let check = new Array(arr.length).fill(0);
  //모든 부분집합이 담길 배열이다.
  let powerSetArr = [];
  const dfs = (depth) => {
    //check에 1인 index와 같은 index에 있는 arr만 filter해서 넣어준다.
    if (depth === check.length) {
      powerSetArr.push(arr.filter((v, idx) => check[idx]));
    } else {
      //포함되는 경우
      check[depth] = 1;
      dfs(depth + 1);
      //포함되지 않는 경우
      check[depth] = 0;
      dfs(depth + 1);
    }
  };
  dfs(0);
  return powerSetArr;
}

마무리

트리 구조 사진과 코드를 함께 보면 이해가 보다 수월할 것이다.
인덱스 기준으로 체크리스트를 만들어 활용하는 것이 멱집합을 구현하는 point가 아닐까 생각해본다.

추가

leetcode를 풀면서 더욱 간단하게 구현할 수 있게 돼 코드를 추가로 남긴다.

const subsets = (nums) => {
  const res = [];

  const dfs = (start = 0, arr = []) => {
    res.push(arr);
    
    //if (arr.length === nums) return; 해도되고 안써도 된다. 속도는 조금더 좋을듯

    for (let i = start; i < nums.length; i++) {
      dfs(i + 1, [...arr, nums[i]]);
    }
  };
   dfs();

  return res;
};