Bootcamp

Searchโฆ

A.9.1: Recursive Backtracking

Introduction

Backtracking is a way to explore valid possible subtrees or permutations. Problems that use backtracking are such things as: permutations of strings, maze solving, sudoku puzzles, chess move validity.

In certain problems such as Generate Parentheses, backtracking may mean we can avoid recursively exploring every subtree. In other problems such as Permutations, this may mean we explore every subtree, and "backtrack" when we have exhausted each subtree.

Permutations

String Permutations

Matched Parens

Maze Solving

Sudoku (harder problem)

N-Queens (harder problem)

Find Tile Permutations Example

You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.

Input: โAABโ, Output: 8. Explanation: "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

def numTilePossibilities(self, tiles: str):

# Store the possible sequences in a set to ensure no duplicates

sequences = set()

# Perform depth-first search

# current is an array of tiles chosen so far

# remaining is an array of remaining tiles

def find_possibilities(current, remaining):

# If current is non-empty, it is a valid sequence.

# Convert it to string and add to sequences.

if current != []:

sequences.add("".join(current))

# If there are no letters remaining, we have exhausted all possible

# sequences in this subtree and can return.

if remaining == "":

return

# For each letter in remaining, add it to current and find

# possibilities that start with letters in the new current.

for i in range(len(remaining)):

current.append(remaining[i])

find_possibilities(current, remaining[:i] + remaining[i+1:])

# After finding possibilities for new current, reset current

# by popping the last-added letter, before appending the next

# letter in remaining. This is the backtracking step.

current.pop()

# Kick off our search by providing an empty array for current and

# the original tiles string containing possible letters.

find_possibilities([], tiles)

# Return the number of unique sequences that we found from our search.

return len(sequences)

Exercises

Pre-Class

- 1.
- 2.
- 1.
- 2.
- 3.

Part 1

- 2.
- 1.Hint: Can we use a for loop to generate the first of
`k`

numbers, use a recursive function to generate the remaining`k-1`

numbers, and combine the first and`k-1`

numbers after the recursive call?

- 3.
- 1.Hint: Same strategy as Combinations

More Comfortable

- 1.
- 1.Hint: Same strategy as Combinations

- 2.
- 1.

- 3.
- 4.

Further Reading

Last modified 2mo ago