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 2^{n} subsets for `nums`

of length *n*. 2^{n} 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]`

:

Number | Binary | Subset |
---|---|---|

0 | 000 | `[]` |

1 | 001 | `[3]` |

2 | 010 | `[2]` |

3 | 011 | `[2, 3]` |

4 | 100 | `[1]` |

5 | 101 | `[1, 3]` |

6 | 110 | `[1, 2]` |

7 | 111 | `[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 2^{n – 1} times (within the `map`

). Therefore, the runtime is the sum of 2^{0} + 2^{1} + … + 2^{n – 1}, which (*waves hand mysteriously*) evaluates to 2^{n} – 1. This translates to O(2^{n}).