Javascript Interview Question:Get all subsets of array

Problem Statement:

For given one dimesional array of numbers find all possible subsets

of that array.

e.g.

For Array [1,2,3]

Output should be

[

[],

[1],

[2],

[3],

[1,2],

[1,3],

[2,3],

[1,2,3]

]

Here array [1,2] & [2,1] are same as per set theory so should not be repeated.

Solution:

function getAllSubsets(arr) {

let subset = [[]];

function generateSubsets(indx, currentSubset) {

if (indx == arr.length) {

return;

}

for (let i = indx; i < arr.length; i++) {

currentSubset.push(arr[i]);

subset.push([...currentSubset]);

generateSubsets(i + 1, currentSubset);

currentSubset.pop();

}

}

generateSubsets(0, []);

return subset;

}

// Example usage:

const inputArray = [1, 2, 3];

const subsets = getAllSubsets(inputArray);

console.log(subsets);

Output:

[

[], [ 1 ],

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

[ 1, 3 ], [ 2 ],

[ 2, 3 ], [ 3 ]

]

Solution (Without Recursion):

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;

}

let array = [1, 2, 3];

let result = getAllSubsets(array);

console.log(result);

Output:

[

[], [ 1 ],

[ 2 ], [ 1, 2 ],

[ 3 ], [ 1, 3 ],

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

]

Explanation:

Here is an example for [1, 2, 3]

1) Start with an empty subset: []

2) Create new subsets by adding "1" to each existing subset.

It will be:[] [1]

3) Create new subsets by adding "2" to each existing subset.

It will be:[], [1] [2], [1, 2]

4) Create new subsets by adding "3" to each existing subset.

It will be: [], [1], [2], [1, 2] [3], [1, 3], [2, 3], [1, 2, 3]