yuliakononchuk

Posted on

# 8.4 Power Set

###### NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Write a method to return all subsets of a set.

So, what exactly is meant under all subsets of a set? According to Wikipedia's definition of the power set, given an array `[1,2,3]`, the method should return an array of all the possible combinations of the elements of that array + an empty array: `[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]`. After drawing it on the paper, I observe a certain pattern for adding each next number:

Basically, with every next element n of the given array we need to add to the resulting array a copy of all already stored combinations with n added to each. We can turn this logic into the code:

``````function allSubsets(arr){
const maxIndex = arr.length - 1;
let result = [ [] ];
arr.forEach(el => {
result.forEach(subset => {
result.push([...subset, el]);
})
})
return result;
}
``````

An alternative recursive solution using the same logic will look like:

``````function allSubsets(arr) {
if (arr.length === 0) { return [ [] ]; }
const prev = allSubsets(arr.slice(1));
const next = prev.map(el => [...el, arr[0]]);
return [...prev, ...next];
}
``````

So, to get all subsets of array `[n...k]` (where n and k are min and max index), we will need to:

1) calculate all subsets of array `[n+1...k]`
2) create a copy of 1)
3) Add `n` to each subset of a copy
4) Merge 1) and 3)