Subsets

Lesson 11.2 · Medium · Include or exclude · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

List every subset of the numbers. These examples stay small on purpose: n items always produce 2^n subsets.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

in30

Choose to include 3.

path [3] · found 0

1 / 95

The idea

Complexity

Time	Space	Why
`O(n × 2^n)`	`O(n)`	2^n subsets, each copied in O(n); the path is the extra space.

In Python

def subsets(nums):
    res, path = [], []
    def dfs(i):
        if i == len(nums):
            res.append(path[:]); return
        path.append(nums[i]); dfs(i + 1)     # include
        path.pop();           dfs(i + 1)     # exclude (backtrack)
    dfs(0)
    return res

</> Now code it →Try it on LeetCode: Subsets →

Summary: say it in the interview

For each item make two choices in turn: include it, then leave it out. After each choice, recurse on the next item. When you come back, undo the choice (backtrack) before trying the other one.
Time O(n × 2^n), space O(n). 2^n subsets, each copied in O(n); the path is the extra space.