Python backtracking and subsets

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

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]]

Explanation

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.

Explore the dry run

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]]

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.

Python backtracking and subsets

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading