부분집합 알고리즘

function powerSet(arr) {
    const obj = {}
    //This loop is to take out all duplicate number/letter
    for (var i = 0; i < arr.length; i++) {
        obj[arr[i]] = true;
    }
  
    //variable array will have no duplicates
    const array = Object.keys(obj);
    const result = [
        []
    ];
    for (let i = 0; i < array.length; i++) {
        //this line is crucial! It prevents us from infinite loop
        const len = result.length;
        for (let x = 0; x < len; x++) {
            result.push(result[x].concat(array[i]))
        }
    }
    return result;
}

 

알고리즘을 풀다보면 부분집합을 이용하는 유형이 많이 나온다. 기본적으로 부분집합 알고리즘은 숙지하고 있어야 한다.