A JS implementation of powerSet, using tail recursion

power_set_using_tail_recursion.js

//[...] =>[[], []]

// [] => [[]]
// [1] => [[], [1]]
// [1, 2] => [[], [1]] + [2] + [1, 2]
// [1, 2, 3] => [[], [1], [2], [1, 2]] + [3] + [1, 3] + [ 1, 2] + [1, 2, 3]


function powerSet(arr) {
  if (arr.length === 0) {
    return [[]];
  }

  let lastItem = arr.pop();
  let res = powerSet(arr);

  newRes = res.map((itemArr) => {
    // this is to create a clone of the array to prevent mutation of the elements of the original array `res`
    let currentArr = itemArr.slice();
    currentArr.push(lastItem);
    return currentArr;
  });

  return res.concat(newRes);
}

function powerSetTailRecursive(arr, acc = [[]]) {
  if (arr.length === 0) {
    return acc;
  }

  let lastItem = arr.pop();

  let newAcc = acc.map(itemArr => {
      let currentArr = itemArr.slice();
      currentArr.push(lastItem)
      return currentArr
  })

  newAcc = acc.concat(newAcc);
  return powerSetTailRecursive(arr, newAcc);
}

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