Python · Course navigation

Python backtracking and subsets

Choose, recurse, and undo to explore a decision tree.

On this page

Before you start

Recursion and mutable lists.

Choose, recurse, and undo to explore a decision tree.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Backtracking explores alternatives while maintaining a partial choice. This subset generator first excludes an item, then includes it, and removes it before returning.

Copy the current path when recording a result. Storing the mutable path object itself would make results share the same changing list.

Code example

Python

def subsets(values):
    result = []
    path = []
    def visit(index):
        if index == len(values):
            result.append(path.copy())
            return
        visit(index + 1)
        path.append(values[index])
        visit(index + 1)
        path.pop()
    visit(0)
    return result

print(subsets([1, 2]))
assert subsets([]) == [[]]

Output

[[], [2], [1], [1, 2]]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1def subsets(values):

2 result = []

3 path = []

4 def visit(index):

5 if index == len(values):

6 result.append(path.copy())

7 return

8 visit(index + 1)

9 path.append(values[index])

10 visit(index + 1)

11 path.pop()

12 visit(0)

13 return result

15print(subsets([1, 2]))

16assert subsets([]) == [[]]

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Begin with no selected values.	`path = []`	—
Exclude both values and record the empty subset.	`result = [[]]`	—
Include 2 after excluding 1.	`path = [2]`	—
Record [2], then undo that choice.	`result = [[], [2]]`	—
Include 1 at the first level.	`path = [1]`	—
Exclude 2 and record [1]; then include 2 and record [1,2].	`result = [[], [2], [1], [1, 2]]`	—
Undo choices while returning to the caller.	`path = []`	—
Print the generated subsets.	`path = []`	[[], [2], [1], [1, 2]]

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

O(n*2^n) time and output storage; O(n) auxiliary recursion/path space excluding output.

Omitting pop leaks a choice into later branches.
Repeated input values can produce equal subsets; this example treats positions as distinct choices.

Try it yourself

How many subsets are produced for three distinct values?

Reveal answer and reasoning

There are 2^3 = 8, including the empty subset and the full set.