Skip to content
Tutorials Center
My learning

Topics

Lesson 67 of 225 ยท Recursion and Backtracking

More Backtracking Classics

Practice backtracking in Python with graph m-coloring, tug of war, removing invalid parentheses, cryptarithmetic puzzles and partitioning into k equal subsets.

You have met the backtracking template already: choose, explore, undo. This lesson applies it to five problems that show up again and again in interviews and puzzle books. Each one looks different on the surface, yet each is the same loop with a different definition of "choice" and a different pruning rule.

As you read, keep two questions in mind. First, what is one decision, and what are its options? Second, how soon can I tell that a partial answer is hopeless? The faster you notice a dead end, the less work the search does. If the template is still new, revisit Backtracking and Subsets, Permutations and Combinations first.

Graph m-coloring

Give each vertex of a graph one of m colors so that no edge joins two vertices of the same color. This models scheduling (exams that share students need different time slots) and register allocation in compilers.

The decision is: which color does vertex v get? Before assigning a color, check it against the neighbors that are already colored. If no color fits, return and let the previous vertex try something else.

Python Color a graph with m colors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the worst case this is O(m^n), and deciding whether m = 3 colors are enough is NP-complete (see NP-Completeness). Backtracking works fine for small graphs because most colorings are rejected after a few vertices.

Tug of war: the best split of a set

Split n numbers into two groups whose sizes differ by at most one, so that the two group sums are as close as possible. Here a decision is "does item i go in the left group or not?". Two prunings keep the search small: stop adding to the left group once it is full, and give up when the remaining items cannot fill it.

Python Tug of war with pruning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The search looks at every group of n/2 items, so it costs about C(n, n/2) steps. For larger inputs a dynamic-programming approach on the sum (Knapsack style) is better when the values are small.

Remove invalid parentheses

A string has brackets and letters, such as "()())()". Delete the fewest characters so the brackets balance, and list every distinct result.

First count how many ( and ) are surplus with a single scan. Then backtrack: at each bracket, either keep it or delete it, and only delete while the surplus counters say you still must. Because those counters are exact, the search never wanders into hopeless branches. A set removes duplicates that come from deleting equal neighbors.

Python Minimum removals to balance brackets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare this with brute force, which tries all 2^n subsets of characters to delete. The counters turn "try everything" into "try only the deletions that can still work".

Cryptarithmetic puzzles

In SEND + MORE = MONEY each letter stands for a different digit and no number starts with 0. The decision is: which unused digit does the next letter get? You can check the full equation at the end (slow), or prune cleverly. The simplest strong pruning is to assign letters in order and test only at the leaves, so first see how far that goes.

Python Solve SEND + MORE = MONEY

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trick is the weight table: the equation becomes a single sum sum(weight[letter] * digit) == 0, so one running total replaces re-reading every word. At most 10!/(10-8)! = 1,814,400 assignments exist for eight letters, and a pure-Python search finishes in a few seconds at worst.

Partition into k equal-sum subsets

Can you split a list into k groups that all have the same sum? Think of k buckets, each with capacity total / k. Place the items one at a time, trying every bucket. Three prunings matter a lot:

  1. If total % k != 0, or any item exceeds the target, the answer is no at once.
  2. Sort items in descending order, so big items fail early.
  3. Skip a bucket whose current sum equals one you already tried for this item (identical buckets give identical futures).
Python k equal-sum subsets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Worst case is still exponential, but these three rules make typical inputs fast. For many small items, a bitmask DP over subsets (Bitmask DP) is the other standard tool.

Palindromic partitions of a string

Cut a string into pieces so that every piece is a palindrome, and list all ways to do it. At each start position, try every end position whose slice is a palindrome, take it, and recurse on the rest; undo the choice on the way back. The only trick is the palindrome test. Checking each slice costs O(n), so precompute a table pal[i][j] once: a slice is a palindrome when its two end characters match and the inside pal[i+1][j-1] is a palindrome (or has length 0 or 1). That makes the test O(1).

Python All palindromic partitions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the worst case (a string like "aaaa") there are 2^(n-1) partitions, so the output itself is exponential. If you only need the fewest cuts, switch to dynamic programming on the same table; see string DP.

Common mistakes

  • Forgetting to undo. Every color[v] = c or used[d] = True needs a matching reset after the recursive call.
  • Checking the constraint only at the leaf. Reject a partial answer the moment it breaks a rule; that is where the speed comes from.
  • Duplicate results. Problems like parentheses removal generate the same string many ways. Collect into a set, or skip equal neighbors.
  • Returning the shared list. When you save path, store a copy (path[:] or "".join(path)), or later undo steps will change what you saved.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In m-coloring, when do you reject a color for vertex v?

    Only already colored neighbors can conflict. Vertices that are not adjacent may share a color.
  2. 2. Why is the surplus count in remove-invalid-parentheses useful?

    Knowing the minimum deletions in advance means every branch either deletes a bracket it must delete or keeps it, which prunes hopeless branches.
  3. 3. What does the weight table in the cryptarithmetic solver do?

    Each letter contributes place value times digit (negative for the result word), so a single total replaces re-reading every word.
  4. 4. Why skip a bucket whose sum equals one already tried for the same item?

    Two buckets with the same current sum lead to identical futures, so the second try can only fail the same way.

Summary

  • Every backtracking problem is a decision, a validity check, a recursive call and an undo.
  • Prune as early as possible: check colors against colored neighbors, stop a group when it is full, count required deletions up front.
  • Precompute whatever turns a check into a single comparison, as the weight table does for cryptarithmetic puzzles.
  • Sorting large items first and skipping equivalent choices make partition problems much faster.
  • For bigger inputs, switch to dynamic programming, bitmasks or meet in the middle.

Next: Sudoku and Puzzles