Problem

Given a set of distinct integers, return all possible subsets.
Example input: [1,2,3]
Example output: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

Solution

// Solution:
// This is a recursive solution.
// The base case is when the input array is empty.
// The recursive case is when the input array is not empty.
// In the recursive case, we take the first element of the array and add it to the result of the recursive call.
// We then add the result of the recursive call to the result.
// This is optimal because it is O(2^n) time and O(2^n) space.

function subsets(arr) {
  if (arr.length === 0) {
    return [[]];
  }
  const first = arr[0];
  const rest = arr.slice(1);
  const subs = subsets(rest);
  const withFirst = subs.map(sub => [first].concat(sub));
  return subs.concat(withFirst);
}

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