Skip to content
dsa450for five year olds

Topic 12 of 15

Backtracking

Exploring a maze and walking back.

Backtracking is exploring a maze with a ball of string. At every fork you pick a path. If it dead ends, you follow the string back to the last fork and try the next path. The art is noticing a dead end early so you do not walk the whole thing.

What you will be able to do

Choose, explore, unchoosePruning earlyPermutations and subsetsBoards: N Queens, SudokuGrids and mazes
0/19
19 problems

Meet the choice tree

01 / 04

tree
-

Make every order of the letters a, b, c. Start with nothing chosen.

  • looking now
  • seen
  • done
  • answer
  • path

The problems

In order from easier to harder ideas. The ones marked must do come up in interviews again and again.

  1. 01Rat in a maze ProblemHelp a rat find every way through a square maze from the top left to the bottom right, stepping on each cell at most once.Backtracking
  2. 02Printing all solutions in N-Queen ProblemPlace n queens on an n by n chessboard so that no queen can attack another, and list every way to do it.Backtracking
  3. 03Word Break Problem using BacktrackingPut spaces into a long run of letters so that every piece is a real word from the dictionary, and list every way to do it.Backtracking with memoization
  4. 04Remove Invalid ParenthesesErase as few brackets as possible so every opening bracket has a matching closing bracket, and list every way to do it.Backtracking
  5. 05Sudoku SolverFill the empty squares of a sudoku so that no digit repeats in any row, column or box, going back whenever a square has no digit left.Backtracking
  6. 06m Coloring ProblemPaint every dot of a map with one of m crayons so that no two dots joined by a line get the same crayon.Backtracking
  7. 07Print all palindromic partitions of a stringCut a word into pieces so that every piece reads the same forwards and backwards, and list every way to do it.Backtracking
  8. 08Subset Sum ProblemDecide if you can pick some of the numbers so that they add up to exactly the target.2D dynamic programming
  9. 09The Knights tour problemMove a chess knight around a board so it lands on every square exactly once.Backtracking
  10. 10Tug of WarSplit kids into two teams of equal size so that the two teams weigh as close to the same as possible.Backtracking
  11. 11Find shortest safe route in a path with landminesCross a field from the left edge to the right edge in the fewest steps, never stepping on a mine or right next to one.Breadth first search
  12. 12Combinational SumFind every bag of coins, where each coin type can be used again and again, that adds up to exactly the price.Backtracking
  13. 13Find Maximum number possible by doing at-most K swapsSwap the digits of a number at most k times to make it as big as possible, trying every copy of the biggest digit when there is a tie.Backtracking
  14. 14Print all permutations of a stringList every way to line up the letters of a word, using each letter exactly once.Backtracking
  15. 15Find if there is a path of more than k length from a sourceStarting from one stop on a map of roads, find out if you can walk farther than k without ever visiting a stop twice.Backtracking
  16. 16Longest Possible Route in a Matrix with HurdlesWalk from a start cell to a goal cell in a grid with walls, taking the longest possible route without ever stepping on the same cell twice.Backtracking
  17. 17Print all possible paths from top left to bottom right of a mXn matrixList every way to walk from the top left corner of a grid to the bottom right corner when you may only step right or down.Backtracking
  18. 18Partition of a set into K subsets with equal sumShare a pile of candy bags among k kids so every kid gets exactly the same amount of candy, without opening any bag.Backtracking with bitmask memo
  19. 19Find the K-th Permutation Sequence of first N natural numbersLine up every order of the numbers 1 to n like words in a dictionary, and jump straight to the k-th one without writing the others.Factorial number system
Next topicTrie