LC-78, Subsets, PowerSet

Subset.js

// LC-78
// https://leetcode.com/problems/subsets/
// Unique subsets

(function() {
  var subsets = function(nums) {
    if (nums.length == 0) {
      return [[]]; // empty
    }
    let first = nums.slice(0, 1),
      rest = nums.slice(1);
    let subs = subsets(rest),
      out = [];
    for (let i = 0; i < subs.length; ++i) {
      out.push(subs[i]);
      out.push(subs[i].concat(first));
    }

    return out;
  };
  console.log(JSON.stringify(subsets([1,2,3,4])));
})();

Subset_succinct.js

(function() {
  var subsets = function(subs, nums) {
    if (nums.length == 0) {
      return subs;
    }
    //console.log(subs)
    return subsets(subs, nums.slice(1))
      .concat("|")
      .concat(subsets([...subs, nums[0]], nums.slice(1)));
  };
  console.log(
    subsets([], [1, 2, 3, 4])
      .join(",")
      .split("|")
  );
})();

O(N * 2^N)