The Leetcode July Challenge problem I’m reviewing today is a fairly simple discrete math problem once you see the underlying logical concept that the algorithm is based on. The problem presents an array of distinct integers and asks us to return the powerset, where the powerset is the set of all possible valid subsets. It’s a little mathy, but discrete math is what we’re all about! We can break this problem down into a logical representation of possible sets. The powerset, $P(S)$, of a valid set, $S = [a, b, c]$, can be described as the logical set values from $[0,0,0]$ to $[1,1,1]$. We can see this by a simple example:

				Set = [1, 2, 3]
LogicalSet = [0, 0, 0]	Set = []
LogicalSet = [0, 0, 1]	Set = [3]
LogicalSet = [0, 1, 0]	Set = [2]
LogicalSet = [0, 1, 1]	Set = [2, 3]
LogicalSet = [1, 0, 0]	Set = [1]
LogicalSet = [1, 0, 1]	Set = [1, 3]
LogicalSet = [1, 1, 0]	Set = [1, 2]
LogicalSet = [1, 1, 1]	Set = [1, 2, 3]

Pretty cool, right!? The logical/binary representation tells us that we can expect O(2^n) elements of the powerset, which will also be our runtime complexity. From that example, we can extrapolate an algorithm that consumes array elements in an ordered fashion:

				Set = [1, 2, 3]
LogicalSet = [0, 0, 0]	Set = []
LogicalSet = [1, 0, 0]	Set = [1]
LogicalSet = [0, 1, 0]	Set = [2]
LogicalSet = [1, 1, 0]	Set = [1, 2]
LogicalSet = [0, 0, 1]	Set = [3]
LogicalSet = [1, 0, 1]	Set = [1, 3]
LogicalSet = [0, 1, 1]	Set = [2, 3]
LogicalSet = [1, 1, 1]	Set = [1, 2, 3]

In code:

vector<vector<int>> subsets(vector<int>& nums) {
   vector<vector<int>> powerset{{}};
   for(auto n : nums) {
	  int setCount = powerset.size();
	  for(int i=0;i<setCount;i++) {
		 powerset.push_back(powerset[i]);
		 powerset.back().push_back(n);
	  }
   }
   return powerset;
}

I really enjoyed that! It’s an algorithm that fits neatly into its discrete mathematics underpinnings. Hopefully we get more of these fun little problems in the July Challenge.