Given a set of integers, find all possible subsets within the set.

subsets-of-ints.js

export function findAllSubsets(v) {
  if (v.length === 0) {
    return [[]];
  }

  const sets = [];

  // total number of subsets is 2^n
  const subsetsCount = 2 ** v.length;
  console.log("total subsets", subsetsCount);

  for (let i = 0; i < subsetsCount; ++i) {
    // we're going to use binary representation of i as a bit mask
    // then we're going to iterate over v, and check corresponding bits in bit mask
    // so for example, if i=1, binary of i is 1.
    // we can then pad it with zeros from the left, like so
    // 001 (pad until length is the same as v.length)
    // 001 tells us that to the set number 1 (i=1) we should only take the first element from v
    // because only the first bit is enabled
    // another example, 101, means we need to include first and last elements of v into set
    const numSet = [];
    console.log(Array(10).fill("-").join(""));
    console.log(`building subset i=${i}...`);
    console.log(`iBinary=${i.toString(2).padStart(v.length, "0")}`);
    for (let j = 0; j < v.length; ++j) {
      // create a binary representation of j that will allow us to check bits in bit mask
      // so we take number 1, and push zeros from the right, shifting it to the left
      // for example, let's say our v.length is 3, so j will be 0, 1, and 2
      // when j=0, value jBinary will be binary 1
      // when j=1, value jBinary will become binary 10
      // when j=2, value jBinary will become binary 100
      // so when for example, i=0, we will compare binary representation of 0 with 1, 10 and 100
      // in this case, there are no common enabled bits
      // when i=1, binary of 1 is 1, we will compare it with 1 (match), 10 (no match), and 100 (no match)
      // so we will kind of compare 1 with 1, 01 with 10 and 001 with 100
      // when i=5, binary of 5 is 101, so we will compare 001 with 101 (j=0), 010 with 101 (j=1), and 100 with 101 (j=2)
      // we need to pick j=0 and j=2 because those have common shared bits set to 1
      // to pick we use & operand, it will produce 0 if there are no shared bits
      const jBinary = 1 << j;
      const shouldPick = (jBinary & i) > 0;

      console.log(`jBinary=${jBinary.toString(2).padStart(v.length, "0")}`);
      console.log(`has matching bits? ${shouldPick ? "yes" : "no"}`);

      if (shouldPick) {
        numSet.push(v[j]);
      }
    }
    console.log(`set ${i} is ready:`, numSet);
    sets.push(numSet);
  }

  return sets;
}