WTF is ‘base case and build’ (CTCI power set problem)

This is a problem from Cracking the Coding Interview that I did not manage to solve nicely on my own.

It is an example of a problem that can be solved using the ‘base case and build’ method.

I have implemented it in TypeScript, based on the given solution in CTCI (so I cheated basically).

I’m going to try and explain the solution back to myself in a way I understand so I hopefully can make it stick and solve similar problems in the future.

Power Set: Write a method to return all subsets of a set.

SPOILER: This is how you can do it recursively:

const powerSet = (set: number[], index: number): number[][] => {
  let allSubsets: number[][];

  if (set.length === index) {
    allSubsets = [];
    allSubsets.push([]);
    return allSubsets;
  } else {
    allSubsets = powerSet(set, index + 1);
    const moreSubsets = [];
    for (let i = 0; i < allSubsets.length; i++) {
      const newSubset = [];
      newSubset.push(...allSubsets[i]);
      newSubset.push(set[index]);
      moreSubsets.push(newSubset);
    }
    allSubsets.push(...moreSubsets);
    return allSubsets;
  }
};

What’s going on here then?

This is an example of using the ‘base case and build’ method of solving problems, where you take the simplest meaningful case of the problem and solve it, then figure out how to move from that simple case to the next iteration, and build a (probably recursive) implementation to take you from n-1 to n.

For simplicity, I’m using arrays to represent sets.

If we need to find all subsets of an empty set ([]), i.e. n=0, we get one subset: []. Our method should return [[]] in this case.

Now n=1. Let’s try with the set [1]. i.e. a set with cardinality of one, with a single element, the integer 1.

This gives us two subsets, the empty set [], and the set [1]. So our method here should return [[], [1]].

Now n=2. We’ll try the set [1,2]. A set with cardinality 2 with two elements, the integers 1 and 2.

This gives us four subsets:

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

At this point, believe it or not we have enough information to solve this problem for any n

As our n increases, we just have to clone all subsets from n-1, then append the nth element to each of the new subsets.

In our case:

n=3, let’s use the set [1,2,3].

Clone [[], [1], [2], [1,2]] and put it into the array:

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

Now append the nth element (3) to all of the cloned subsets:

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

Now we have a base case (below is shitty pseudocode btw, not TypeScript):

if (n===0) { subsets.push([]) }

and we can use our newly discovered transformation to construct the remaining subsets recursively.

else {
  cloned = subsets.clone();
  append set[n] to each subset;
  subsets.append(cloned);
}

In terms of time and space complexity, this solution uses O(n * 2^n) space and O(n * 2^n) time, which is the same as the total number of elements across all subsets.

I need to think a bit more about why exactly this is the case, but visually you can see the rate at which it grows by drawing out n from 0 up to 4

[[]]

[[], [1]]

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

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

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