Go to “Subsets (#78)” on Leetcode ↗

This is a problem where I think the brute-force solution is actually harder to implement than the better solution.

Solution 1: Brute Force

One brute force solution is to implement a solution that somewhat literally follows the problem. One way to think about “all possible subsets” is by coming up with all the sets of length 1 first, then all the sets of length 2, and so up until all sets of length n (where n is the length of nums). It’s conceptually simple, but the code to implement this is actually quite messy, so we won’t bother with it here. There’s also some obvious unnecessary work — for example, every set of length 3 contains sets of length 2; in other words, every set of length x contains some sets of length x – 1, and we should be able to reuse the effort to generate the x – 1 sets in some way.

Solution 2: Dynamic Programming

The key insight for this solution is that every element in nums can either be in a particular subset, or not be in that subset, ranging from a case where every element in nums is not in a subset (leading to the empty subset []), to a case where every element in nums is in a subset (leading to a subset that contains everything in nums), and everything in between. That is one of the properties of a power set. You may happen to know/remember this fact. One other way of coming across this insight is by noticing that in the example with three elements in nums, there are eight subsets. You can try generating subsets manually for two or four nums, and see that there are 2n subsets for nums of length n. 2n is represented in binary as a number n digits long, each 0 or 1, and every value between 0 and n, translated to binary, is a description of a particular subset. For example, in the case where nums is [1, 2, 3]:

NumberBinarySubset
0000[]
1001[3]
2010[2]
3011[2, 3]
4100[1]
5101[1, 3]
6110[1, 2]
7111[1, 2, 3]

In fact, we could implement the solution like this — loop from 0 to nums.length, turn that number into binary, and extract the corresponding numbers from nums.

That’s a little messy though. Another way to implement the same idea is to keep track of subsets as we generate them, iterate through nums, and for each number in nums, duplicate all the existing subsets and append the new number to each subset copy. What we’re basically doing is saying that each of the duplicated-and-appended subsets contains the current number, and each subset that it originally came from doesn’t contain the current number. Finally, of course, we have to add the duplicated-and-appended subsets back to the list of all subsets.

def subsets(nums)
  subsets = [[]]
  nums.each do |num|
    subsets.concat(subsets.map { |existing_set| existing_set + [num] })
  end
  subsets
end

This solution can be written more compactly in one line (more or less) using Ruby’s reduce method (see my solution to Problem 8 for an explanation of how it works):

def subsets(nums)
  nums.reduce([[]]) do |subsets, num|
    subsets.concat(subsets.map { |existing_set| existing_set + [num] })
  end
end

This one-liner seems to run a little bit faster on Leetcode, but is a little more difficult to understand at first glance.

Runtime: It’s not particularly clear just by looking at the code. First, we’ll make a simplifying assumption that the concat method runs in constant time — this depends on implementation details, but you could make the case that you could use a linked list for subsets, in which case this could be true. Similarly, we’ll also assume that existing_set + [num] (adding num to existing_set) takes constant time, for the same reason.

Within each of n loop iterations, we are thus performing constant-time operations 2n – 1 times (within the map). Therefore, the runtime is the sum of 20 + 21 + … + 2n – 1, which (waves hand mysteriously) evaluates to 2n – 1. This translates to O(2n).