Basics 0/97

Recursion · 2 of 3

Recursive brute force

Try every combination of choices with one decision per call: list the subsets with a shared list, return a count or a best value, and loop over more than two options.

1,677 words · 8 min read

Part 1 of 7 Recursive brute force

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.

Difficulty tier:Normal

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

  • 1≤1 \le len(nums) ≤10\le 10
  • −10≤-10 \le nums[i] ≤10\le 10
  • The numbers in nums are 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 2×2×2=82 \times 2 \times 2 = 8 subsets, the eight lists of the first sample, and the 10 numbers the problem allows have 210=1,0242^{10} = 1{,}024.

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 2n−12^n - 1 and reading each number as a bit mask: bit ii of the number is 1 when nums[i] is in the subset, so the 2n2^n numbers give the 2n2^n 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.