부분집합

코딩테스트를 보다가 부분집합에 대한 문제가 나왔다.
이제 문제 자체에 답변을 내는건 가능한데 꼭 효율성 문제가 내 발목을 잡고 있다.

내가 부분 집합을 구현했던 방법은 recursion을 활용했던 방법으로 js 엔진이 1만개 정도의 recursion call에서 에러를 뱉어낸다.

recursion 없이 부분집합을 구하는 방법(가장 효율성을 극대화한)을 찾던 중에 관련 주제의 stackoverflow를 발견했다.

https://stackoverflow.com/questions/42773836/how-to-find-all-subsets-of-a-set-in-javascript-powerset-of-array

+) 추가로 집합을 이용하는 문제들은 set 객체를 이용하는 방법을 가장 먼저 고민해보는게 좋을 것 같음. set은 해시테이블이 기본이기 때문에 효율성 문제가 전혀 없다.
https://blog.greenroots.info/everything-you-need-to-know-about-javascript-set

일단 이중 가장 베스트는
1. 반복문을 적절히 사용
O(n^2)

function getAllSubsets(array) {
    const subsets = [[]];
    
    for (const el of array) {
        const last = subsets.length-1;
        for (let i = 0; i <= last; i++) {
            subsets.push( [...subsets[i], el] );
        }
    }
    
    return subsets;
}

2. recursion

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

구글링 했을때 가장 먼저 뜨는 recursion 코드
https://velog.io/@proshy/JS%EB%AA%A8%EB%93%A0-%EB%B6%80%EB%B6%84-%EC%A7%91%ED%95%A9%EB%A9%B1%EC%A7%91%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0

3. 심플하지만 효율성은 떨어지는 방법

const getAllSubsets = 
      theArray => theArray.reduce(
        (subsets, value) => subsets.concat(
         subsets.map(set => [value,...set])
        ),
        [[]]
      );

console.log(getAllSubsets([1,2,3]));

4. generator function 활용
   O(n2ⁿ)

// Generate all array subsets:
function* subsets(array, offset = 0) {
  while (offset < array.length) {
    let first = array[offset++];
    for (let subset of subsets(array, offset)) {
      subset.push(first);
      yield subset;
    }
  }
  yield [];
}

// Example:
for (let subset of subsets([1, 2, 3])) {
  console.log(subset); 
}