Free lessonsBacktracking · Stage 0 · Build, check, undo · Step 2

Generate all subsets

For each item, decide whether to include it or exclude it, backtracking each time. About 9 minutes.

The include / exclude choice

Packing for a trip, you go through your list of items one by one and decide: take it, or leave it. Every item gets exactly two options. Walking from the first item to the last, and making that choice each time, produces every possible bag, which is all 2 to the power n subsets.

Take the item first, explore what follows, then undo and explore without it.

Include: add the item, then move on to the next one.

Exclude: remove it again, then move on to the next one.

nums = [1, 2]: take it (left) or leave it (right), one number per level

result: []

Level 1 decides about 1. Take it first.

Move 1 of 5

Clone your answer!

The working list keeps changing as the algorithm walks back up the tree. If you save the list itself, every saved answer ends up pointing at the same list, which finishes empty. It is like handing out your only notepad and then erasing it.

You must photocopy the list at the moment you reach the end. The empty subset is always one of the answers.

Save a copy, never the working list itself.

Empty subset: taking nothing is always part of the answer.

In code

res = []
def backtrack(idx, curr):
    if idx == len(nums):
        res.append(list(curr))
        return
    curr.append(nums[idx])
    backtrack(idx + 1, curr)
    curr.pop()
    backtrack(idx + 1, curr)
backtrack(0, [])
return res

Quick check

How many subsets does a list of 3 unique numbers have?

A8 subsets
B6 subsets
C7 subsets

Show the answer

8 subsets. Each of the 3 elements has 2 choices (in or out), giving 2³ = 8 subsets.

Your problem

Generate all subsets

Given an array of unique integers nums, return all possible subsets (the power set). List them in the order the include/exclude recursion finds them: for nums[0], first everything that takes it, then everything that leaves it out, and the same for each later number.

Example

nums = [1, 2] → [[1, 2], [1], [2], []]

0 ≤ nums.length ≤ 10 · -1,000,000 ≤ nums[i] ≤ 1,000,000 · All elements are unique

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding