Coding interview Essentials

1. Power set generation

Power set generation

Introduction

As one of the first topics in introductory math courses on set theory, many of us are familiar with what a power set is.

A power set is the set of all the subsets of a set \(S\). In this lesson, we will explore how we can generate the power set of a given set: this is a task we are frequently challenged to solve, directly as well as indirectly, as part of a coding interview question.

We will investigate two different approaches to solve this problem:

  1. The first one derives straightforwardly from the recursive definition of power-set, which states "the power-set of an empty set is a set containing one element only: the empty set itself". For a non-empty set \(S\), let \(e\) be an element of \(S\) and \(T\) be the original set \(S\) set minus \(e\) ( \(T=S \setminus e\)), then the power set of \(S\) is defined as the union of two distinct power sets:

  2. The second approach is based on a bit-distribution property in the integers binary representation from \(0\) to the size of the power set.

\[\mathcal{P}(S)=\begin{cases} \{\{\}\} & \text{if } S=\{\} \\ \mathcal{P}\{T\} \bigcup \{t \bigcup \{e\} \: : t \in \mathcal{P}\{T\}\} \text{ where } T = S \setminus \{e\} \text{ } \forall e \in S, & \text{otherwise} \end{cases} \label{eq:power_set_recursive_definition}\]

Problem statement

Write a function that given a set \(S\) returns its power set. The power-set of \(S\) (\(\mathcal{P}(S)\)) is the set of all its subsets including the empty subset (\(\emptyset\)) and \(S\) itself.

[ex:power_set:example1]
Given the set \(S=\{a,b,c\}\), the following is a correct output for this problem: \[\{\{\}, \{a\}, \{b\}, \{c\}, \{a,b\}, \{b,c\}, \{a,c\}, \{a,b,c\} \}\]

Clarification Questions

What is the maximum input size?

The maximum number of elements in \(S\) is strictly less than \(32\).

Are all the elements in the collection distinct?

No, the elements are not necessarily distinct. \(S\) might contain duplicates.

Can the elements of the power-set appear in any order?

Yes, subsets can appear in any order. For example the following is also a valid output for the input shown in Example [ex:power_set:example1]: \(\{\{\}, \{b,c\}, \{a\}, \{a,b\}, \{a,b,c\}, \{b\}, \{a,c\}, \{c\} \}\)

Discussion

First thing first, we should notice one key point: The power set of a collection of \(n\) elements has size \(2^n\). The proof is relatively easy, and it boils down to the fact that a subset of \(S\) can be uniquely identified by a list \(X=\{x_0,x_1,\ldots x_{|S|-1}\}\) of \(|S|\) binary variables each carrying the information about whether \(S_i\) is part of the subset; the variable \(x_i\) is crucial to answer the question should \(S_i\) be part of this subset?: If \(x_i\) is true the answer is yes, otherwise, the answer it is no. We have two possible choices for every element of \(S\) (either take it or not), then the total number of distinct \(X\)s is: \(2 \times 2 \times \ldots \times 2 = 2^{|S|}\). Two choices for the first element, two for the second, and so on until the last element of \(S\).

This, together with the constraint on \(|S|\) (\(|S| < 32)\) is a strong hint towards the fact that an exponential time and space solution is expected. After all, we are required to output all the elements of the power set, and thus the number of operations of an algorithm designed for this task cannot be less than the size of the power set itself.

Bruteforce - Backtracking-like approach

The first solution presented in this lesson is based on that, during the generation of one of the power set’s elements, a decision has to be made for each element \(e\) of \(S\), on whether to include or not \(e\) into the subset. Once we determine this, we are left with are \(|S|-1\) decisions before we have created a valid subset of \(|S|\).

This process is inherently recursive and is easily visualized with a tree (see the figure below): a node at level \(i\) represents a decision for the \(i^{th}\) element of \(S\) and a path from the root to a leaf uniquely identifies a subset of \(S\); after having traversed all the levels down to a leaf, \(n\) decisions have been made: one for each of the elements of \(S\).

Collectively, all the paths from the root to the leaves are the power set, and therefore, in order to solve this problem, we have to visit the entire tree.

A general way to deal with such type of problems is using a backtracking-like approach to try all possible decisions (or equivalently to visit every path from the root to a leaf).

The idea is that, for all elements of \(S\), from the first to the last one, we are going to explore the two available possibilities: either take or exclude it from the subset.

We start by making a decision for the first element: From there, we continue to generate all possible subsets where the first decision is never changed. When there are no more subsets to generate, we *backtrack* and change our first decision and repeat the process of generating all possible subsets.

For instance, given \(S=\{1,2,3\}\), we might start by deciding to use the element \(1\), and include it in all possible subsets from the remaining elements \(\{2, 3\}\) only. Once we are done with it, we can repeat the same process, only this time excluding \(1\). What we do is: \(\mathcal{P}(S)= \{\{1\} \; \bigcup \;\mathcal{P}(\{2,3\})\} \: \bigcup \: \{\mathcal{P}(\{2,3\})\}\}\)

The proposed solution will incrementally construct one subset at a time, using an integer variable to keep track of which element we are currently taking the decision for. This type of problem is naturally solved recursively, with a base case of the recursion happening when there is no more decision to make, meaning that the current subset is ready to be included in the solution (it has been produced after \(n\) decision steps).

Here below we can see how the C++ code implements this idea. The complexity of this solution is exponential i.e. \(O(2^{|S|})\) which as already pointed out, is as good as it gets.

Listing 1: C++ to the power set generation using backtracking

void power_set_backtracking_helper(const std::vector<int> &S,
                                   const int idx,
                                   std::vector<int> &curr,
                                   std::vector<std::vector<int>> &ans)
{
  if (idx >= S.size())
  // base case
  {
    ans.push_back(curr);
    return;
  }

  // include element S[idx]
  curr.push_back(S[idx]);
  power_set_backtracking_helper(S, idx + 1, curr, ans);

  // exclude element S[idx]
  curr.pop_back();
  power_set_backtracking_helper(S, idx + 1, curr, ans);
}

std::vector<std::vector<int>> power_set_backtracking(const std::vector<int> &S)
{
  std::vector<std::vector<int>> ans;
  std::vector<int> current;
  power_set_backtracking_helper(S, 0, current, ans);
  return ans;
}
Decision tree for the power-set generation using a backtracking-like brute-force approach. At level i are the decisions for the element i in S. A label marked with "yes" identifies the decision to add the corresponding element into the subset, while a node labeled with "no" identifies the opposite. Each path from the root to a leaf is an element of the power set. At the last level is the power set.

Using a backtracking like approach is convenient because, once we notice that a problem can be solved by fully exploring the associated search space tree, we can immediately start writing the code and rely on our experience as backtracking expert writers to implement a correct solution. It is also concise and short when written in a recursive form (fewer chances to make mistakes, and less code to debug and explain), as well as well understood. The downside is that, if we decide to go for it, an iterative implementation can be a little harder and verbose to write.

Regardless of which type we decide to write, the interviewer is going to be pleased with the code provided: of course it is important to get to the final solution without making too many implementation mistakes, like forgetting to handle the base case.

Bit Manipulation

We can use another approach to solve this problem, based on that the values of the bits of the numbers \(\{0,1,2,\ldots, s^n-1\}\) already provide all the information necessary to decide whether to include or not an element from \(S\) into a subset. The main idea is that the binary representation of all the numbers (\(2^{|S|}\) of them) from \(0\) to \(2^{|S|}-1\) is the power set of \(n\) bits. In a nutshell, this means that the binary representation of any of those numbers carries the necessary information that can be used to build one subset of \(\mathcal{P}(S)\).

For instance, given the input \(S=\{a,b,c\}\) the table below shows numbers from \(0\) to \(2^3-1 = 7\) and their binary representation (in the second column), as well as how the information about which bit is set can be used to construct one subset of \(\mathcal{P}(S)\) (in the third column). When the \(i^{th}\) bit is set (its value is \(1\)), it means that corresponding \(i^{th}\) element of \(S\) is chosen, while an unset bit (with value \(0\)) means it is excluded

This table shows a 1-to-1 mapping between integer values, their binary representation and an element of the power set.
Number Value Bits Subset
0 000 \(\{\}\)
1 001 \(\{c\}\)
2 010 \(\{b\}\)
3 011 \(\{b,c\}\)
4 100 \(\{a\}\)
5 101 \(\{a,c\}\)
6 110 \(\{a,b\}\)
7 111 \(\{a,b,c\}\)

This idea can be used to write an algorithm in which all the numbers in the range \(\{0,1,2,\ldots, 2^{|S|}-1\}\) are considered and each of them is used to generate a subset of the final solution. Every number from this range maps uniquely to a subset of \(\mathcal{P}(S)\).

It is not surprising when we think about the meaning of a bit in the binary representation of integers: One can "build" a number \(k\) by summing up powers of \(2\) where the bits contain the information about whether a certain power of two should be added to the final value. With \(n\) bits one can represent \(2^n\) numbers, each corresponding to one and only one subset of the power set of those \(n\) bits. Listing [list:power_set_bits] shows a possible C++ implementation of the idea above.

Listing 2: Solution using bit manipulation.

constexpr inline bool is_bit_set(const int n, const unsigned p)
{
  return (n >> p) & 1;
}

std::vector<std::vector<int>> power_set_bit_manipulation(
    const std::vector<int> &A)
{
  const size_t limit = (1ll << A.size()) - 1;
  std::vector<std::vector<int>> PS;
  PS.reserve(limit + 1);

  for (int i = 0; i < limit; i++)
  {
    std::vector<int> subset = {};
    for (int p = 0; p < 32; p++)
      if (is_bit_set(i, p))
      {
        subset.push_back(A[p]);
      }
    PS.push_back(subset);
  }

  PS.push_back(A);
  return PS;
}

The complexity of this function is, not surprisingly, \(O(2^{|S|})\). We also pay a constant price of \(32\) for each number we loop through since we need to inspect all of its bits. The proposed implementation assumes that the size of is \(4\) bytes, which is true for most systems.

Moreover, notice the usage : it should be used in all those scenarios when we already know the final size of the collection we are building. This saves time because it avoids intermediate allocations and copies that must happen during the resize of the vector.