A search with one choice per call
Some problems are solved by trying every possible combination of choices: which items to take, in which order, with which letter in each position. Recursion builds each combination one piece at a time. A call makes one decision, tries every option for it in turn, and for each option calls itself to make the decisions that remain. This is recursive brute force. It skips no option, even one that looks hopeless. That makes it slow on large inputs, but it is easy to get right, and faster searches start from it.
We start with a problem that asks for every subset of a list.
Given a list of distinct integers nums, return every subset of it: every list you can make by keeping some of the numbers and leaving out the rest, including the empty list and the whole list. The subsets may come in any order.
Constraints
-
len(nums) -
nums[i] - The numbers in
numsare distinct.
Sample 1 · Input
nums = [1,2,3]
Output
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Sample 2 · Input
nums = [0]
Output
[[],[0]]
Each number is either in a subset or not, so three numbers have subsets, the eight lists of the first sample, and the 10 numbers the problem allows have .
For three numbers, three nested loops could make the three in-or-out decisions. For another length the code would need another number of loops, and code cannot add loops while it runs. A recursive function gets the same effect with one decision per call: the call for the first number tries both choices, and for each of them it calls itself to decide the remaining numbers.
A loop can also list subsets without recursion, by counting from 0 to and reading each number as a bit mask: bit of the number is 1 when nums[i] is in the subset, so the numbers give the subsets. Recursion takes a little more code than that loop, and it handles two things that are awkward with masks. A call can choose among more than two options, and a call can stop as soon as its partial choice cannot lead to an answer, which skips every call below it. A search that stops early in this way is called backtracking.
The tree of decisions
The function keeps a list chosen of the numbers put in so far. The call choose(i) decides nums[i]: it calls choose(i + 1) once with nums[i] left out of chosen and once with it put in. When i reaches the length of nums, every number has been decided, so chosen is one finished subset, and the call records it. That is the base case.
The search starts with choose(0) and an empty chosen. For nums = [1, 2, 3] the calls form this tree, with one level for each value of i from 0 to 3:
chosen when the call starts. A dashed edge leaves the number out and a solid edge puts it in. The 8 boxes on the bottom level are the 8 subsets, recorded from left to right.A call leaves its number out before it puts it in, so the first subset recorded is the empty one and the last is [1, 2, 3]. The problem accepts the subsets in any order. Every subset is recorded exactly once, because the path from the top of the tree to a box on the bottom level makes one choice for each number, and two different paths differ in at least one choice.
A shared list and undoing a choice
All the calls work on the same list chosen. A call adds nums[i] to it before its second recursive call and removes it again afterwards:
def subsets(nums):
result = []
chosen = []
def choose(i):
if i == len(nums):
result.append(chosen[:])
return
choose(i + 1)
chosen.append(nums[i])
choose(i + 1)
chosen.pop()
choose(0)
return result
print(subsets([1, 2, 3]))Whatever a call adds to chosen it also removes, so when the call returns, chosen is exactly as it was when the call started. Its caller can then go on to its own next step as if the call had not happened. Without the removal, a number put in on one branch of the tree would still be in the list on the next branch.
choose is defined inside subsets, so it can use nums, chosen and result without receiving them as parameters. result.append(chosen[:]) records a copy of the list. Appending chosen itself would put the same list into result eight times, and that list is empty again by the time the search ends.
The subset search call by call
The widget runs the search on [1, 2, 3]. The Call stack panel never holds more than four calls, one for each value of i from 0 to 3, and the Recorded subsets panel gains a subset each time a call reaches the bottom level.
A search that returns an answer
Many problems ask for a number, such as how many subsets have some property or how good the best one is, and then there is nothing to record. Each call then needs two things from its caller: the part of the input it still has to decide, and a summary of the decisions already made that holds only what the rest of the search needs. It passes its answer back up as its return value.
For example, let us count the subsets of [3, 1, 4, 2] whose sum is 5. The rest of the search needs only the sum of the numbers put in so far, so each call receives that sum, total, instead of the list. The call count(i, total) returns the number of ways to decide the numbers from nums[i] onwards so that the final sum is the target. At the end of the list there is one way if total equals the target and none otherwise. Before the end, one recursive call counts the ways that leave nums[i] out, another counts the ways that put it in, and the two counts are added.
def count_subsets(nums, target):
def count(i, total):
if i == len(nums):
return 1 if total == target else 0
return count(i + 1, total) + count(i + 1, total + nums[i])
return count(0, 0)
print(count_subsets([3, 1, 4, 2], 5))The program prints 2, for the subsets [3, 2] and [1, 4]. Nothing has to be undone here, because total + nums[i] is a new value handed to one call, and the caller's own total does not change. A search for the best subset, such as the largest sum that stays under a limit, has the same form: where count adds the answers of its two recursive calls, it returns the larger of them.
More than two options per call
A yes-or-no choice takes two recursive calls. When a step has more options, the call loops over them and makes one recursive call for each. As an example we list every string of length made of the letters a, b and c. The call build(prefix) receives the letters chosen so far. A prefix of length is a finished string, and a shorter prefix is extended by each of the three letters in turn:
def strings(n):
result = []
def build(prefix):
if len(prefix) == n:
result.append(prefix)
return
for letter in "abc":
build(prefix + letter)
build("")
return result
print(strings(2))For it lists the nine strings from aa to cc in dictionary order. Each of the positions has 3 options, so there are strings, and the call tree has three branches under every call that is not a base case.
The options can also depend on the choices already made. To list every ordering of some items, the loop runs over the items not yet used, and to place queens on a chessboard it runs over the squares that no earlier queen attacks. The Backtracking lesson covers both.
The cost of a recursive search
- Listing every subset of $n$ numbers
calls, depth - The levels of the tree hold calls, and the bottom level is the subsets. Recording a subset copies up to numbers, so the time is .
- Counting the subsets with a given sum
calls, depth - Each call does a constant amount of work, so the time is . The stack takes memory.
- Listing every string of length $n$ over 3 letters
calls, depth - The levels hold calls, and the bottom level is the strings.
These counts grow so fast that the limits in a problem statement tell you whether a search over every choice can pass. With yes-or-no choices, gives about subsets, which takes a fraction of a second, and gives about , which is too slow at simple operations a second. So a statement with leaves room for trying every subset, even with steps of work for each one: is about .
Common mistakes in a recursive search
Leaving a choice in the list after the call that used it.
- Where it breaks
- Without the removal, every number that is added stays in the list. The search on
[1, 2, 3]records[],[3],[3, 2],[3, 2, 3]and four longer lists. - The fix
- Remove the number right after the recursive call that was made with it, so that every call leaves the list as it found it.
In Python, recording the shared list itself.
- Where it breaks
- With
result.append(chosen), the search on[1, 2, 3]returns eight empty lists. All eight entries are the one shared list, and it is empty when the search ends. - The fix
- Record a copy,
chosen[:]. In C++,push_back(chosen)already stores a copy.
A base case one position too early.
- Where it breaks
- With the base case at the last index of the list, the last number is never decided. The search on
[1, 2, 3]records only[],[2],[1]and[1, 2]. - The fix
- The call with nothing left to decide is the one whose index equals the length of the list.
Recall The subset search runs on a list of 4 numbers. How many subsets does it record, how many calls does it make, and how deep does the stack get?
It records subsets. The tree has calls. The stack is at most 5 calls deep, one for each value of i from 0 to 4.