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``
2010``
3011`[2, 3]`
4100``
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).