TRT
Sign in

Core · Module 7 · Lesson 4 of 4

Backtracking basics

Backtracking builds a solution one choice at a time, explores each choice recursively and undoes it afterwards. Pruning dead ends early is what makes it practical.

Pro — members onlyAbout 15 minutes

By the end you can

  • Write a backtracking search with the choose, explore, unchoose pattern
  • Generate subsets, permutations and combinations, and count how many there are
  • Prune branches that can't lead to a solution, and estimate the cost of a search

Builds on Recursion vs iteration.

01 · A question first

There are 4.4 billion ways to put 8 queens on a chessboard. Only 92 of them leave no two queens attacking each other. A backtracking search finds all 92 after trying only 15,720 queen placements. How does it rule out the other billions without looking at them?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Solving by trying
  • Choose, explore, unchoose
  • Subsets, permutations, combinations
  • Pruning
  • Backtracking in real software
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeSubsetsReturn every subset of a set of distinct integers, using backtracking with a start index.Practice · medium · LeetCodePermutationsReturn every ordering of an array of distinct integers, tracking which elements are already used.Practice · medium · LeetCodeCombination sumFind every combination of candidates, each usable any number of times, that adds up to a target, pruning once the sum is too large.Practice · hard · LeetCodeN-queensPlace n queens on an n × n board so that no two attack each other, and return every solution, pruning by column and diagonal.Practice · medium · LeetCodeWord searchDecide whether a word can be traced through adjacent cells of a letter grid, marking cells as used and unmarking them on the way back.Practice · medium · LeetCodeGenerate parenthesesGenerate every well-formed string of n pairs of parentheses, never building an invalid prefix.

Asked in interviews

Something wrong with this lesson? Report a problem