To ace your coding interview for a software engineering job, you’ll need to understand backtracking. Backtracking is a technique that solves a problem by exploring possible solutions to its subproblems, abandoning any that will not lead to a valid solution. This technique can be used to find a single solution or to do an exhaustive search for all solutions to a problem.
Let’s take a look at some typical backtracking questions.
5 typical backtracking interview questions

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Write a program to solve a Sudoku puzzle by filling the empty cells.

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Given n pairs of parentheses, write a function to generate all combinations of wellformed parentheses
Below, we take a look at 47 backtracking questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:
 Easy backtracking interview questions
 Medium backtracking interview questions
 Hard backtracking interview questions
 Backtracking basics
 Backtracking cheat sheet
 How to prepare for a coding interview
Click here to practice coding interviews with exFAANG interviewers
Let's get started.
1. Easy backtracking interview questions
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of backtracking.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.
Backtracking questions don't tend to be very easy, so we've only included one example in this first section.
Question 1: Binary watch
 Text guide (Medium/Competitive Programming)
 Video guide (Owen Smith)
 Code example (xietao0221)
2. Medium backtracking interview questions
Here are some moderatelevel questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
Question 2: Letter combinations of a phone number
 Text guide (After Academy)
 Video guide (NeetCode)
 Video guide (Kevin Naughton Jr.)
 Code example (lei31)
Question 3: Generate parentheses
 Text guide (RedQuark)
 Video guide (Back to Back SWE)
 Code example (brobins9)
Question 4: Permutations
 Text guide (issac3)
 Video guide (NeetCode)
 Code example (OldCodingFarmer)
Question 5: Subsets
 Text guide (LeetCode)
 Video guide (Nideesh Terapalli)
 Video guide (Kevin Naughton Jr.)
 Code example (issac3)
Question 6: Word search
 Text guide (Programmerall)
 Video guide (NeetCode)
 Code example (OldCodingFarmer)
Question 7: Combination sum
 Text guide (AfterAcademy)
 Video guide (NeetCode)
 Code example (OldCodingFarmer)
Question 8: Word search II
 Text guide (Hary Krishnan)
 Video guide (NeetCode)
 Code example (OldCodingFarmer)
Question 9: Palindrome partitioning
 Text guide (xiaodoubao)
 Video guide (NeetCode)
 Code example (Titanwolf)
Question 10: Combination sum II
 Text guide (LeetCode)
 Video guide (NeetCode)
 Video guide (Kevin Naughton Jr.)
 Code example (lchen77)
Question 11: Permutations II
 Text guide (RedGreenCode)
 Video guide (NeetCode)
 Code example (UpTheHell)
Question 12: Subsets II
 Text guide (Medium/The clubhouse)
 Video guide (Nideesh Terapalli)
 Code example (prime_tang)
Question 13: Gray code
 Text guide (GeeksforGeeks)
 Code example (YuSi)
Question 14: Combinations
 Text guide (Dev.to/Codepineapple)
 Video guide (Xavier Elon)
 Video guide (NeetCode)
 Code example (fabrizio3)
Question 15: Path sum II
 Text guide (Zirui)
 Video guide (Deepti Talesra)
 Video guide (Naresh Gupta)
 Code example (jianchaoli)
Question 16: Combination sum III
 Text guide (Aaronice)
 Video guide (Naresh Gupta)
 Code example (jinwu)
Question 17: Matchsticks to square
 Text guide (Massivealgorithms)
 Video guide (NeetCode)
 Code example (YehudisK)
Question 18: Restore IP addresses
 Text guide (Dev.to/Akhil)
 Video guide (Restore IP Addresses)
 Code example (fiona_mao)
Question 19: Increasing subsequences
 Text guide (Zirui)
 Video guide (Happy Coding)
 Code example (chidong)
Question 20: Beautiful arrangement
 Text guide (LeetCode)
 Video guide (Naresh Gupta)
 Code example (shawngao)
Question 21: Letter case permutation
 Text guide (Tutorialcup)
 Video guide (Algorithms Made Easy)
 Code example (tarekd)
Question 22: All paths from source to target
 Text guide (GeeksForGeeks)
 Video guide (Michael Muinos)
 Code example (lee215)
Question 23: Partition to K equal sum subsets
 Text guide (Medium/Trick The Interviewer)
 Video guide (NeetCode)
 Video guide (Back to Back SWE)
 Code example (GraceMeng)
Question 24: Letter tile possibilities
 Text guide (Shareablecode)
 Video guide (Cogent Coder)
 Code example (LeetCode)
Question 25: Path with maximum gold
 Text guide (Tutorialspoint)
 Video guide (Michael Muinos)
 Code example (hiepit)
Question 26: Maximum length of a concatenated string with unique characters
 Text guide (Programmerall)
 Video guide (Kevin Naughton Jr.)
 Video guide (NeetCode)
 Code example (lee215)
Question 27: Split array into Fibonacci sequence
 Text guide (Fatalerrors)
 Video guide (happygirlzt)
 Code example (touchdown)
Question 28: Split a string into the max number of unique substrings
 Text guide (Another casual coder)
 Video guide (Naresh Gupta)
 Code example (kunqian)
Question 29: Construct the lexicographically largest valid sequence
 Text guide (kamyu104)
 Video guide (Happy Coding)
 Code example (db99)
Question 30: Iterator for combination
 Text guide (Mo4tech)
 Video guide (TECH DOSE)
 Code example (archit91)
Question 31: Splitting a string into descending consecutive values
 Text guide (walkccc)
 Video guide (NeetCode)
 Code example (vikrant_pc)
Question 32: Closest dessert cost
 Text guide (ProgrammerAll)
 Video guide (Cherry Coding)
 Code example (vikrant_pc)
3. Hard backtracking interview questions
Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
Question 33: Word break II
 Text guide (Java questions)
 Video guide (babybear4812)
 Code example (Cheng_Zhang)
Question 34: Sudoku solver
 Text guide (After Academy)
 Video guide (Back To Back SWE)
 Code example (LeetCode)
Question 35: Stickers to spell word
 Text guide (linlaw)
 Video guide (NeetCode)
 Code example (zestypanda)
Question 36: Remove invalid parentheses
 Text guide (Codertrain)
 Video guide (WorkWithGoogler)
 Video guide (happygirlzt)
 Code example (dietpepsi)
Question 37: Expression add operators
 Text guide (Medium/Nitish Chandra)
 Video guide (Coding Decoded)
 Code example (hiepit)
Question 38: NQueens
 Text guide (Dev.to/seanpgallivan)
 Video guide (NeetCode)
 Code example (prime_tang)
Question 39: Unique paths III
 Text guide (Medium/Anj)
 Video guide (Naresh Gupta)
 Code example (archit91)
Question 40: 24 Game
 Text guide (dume0011)
 Video guide (happygirlzt)
 Code example (zhang)
Question 41: NQueens II
 Text guide (Dev.to/seanpgallivan)
 Video guide (code Explainer)
 Code example (AlexTheGreat)
Question 42: Verbal arithmetic puzzle
 Text guide (hiepit)
 Video guide (Algorithms Class)
 Code example (Wangyi)
Question 43: Longest subsequence repeated K times
 Text guide (walkccc)
 Video guide (Happy Coding)
 Code example (DBabichev)
Question 44: Number of squareful arrays
 Text guide (Medium/Nitish Chandra)
 Code example (lee215)
Question 45: Find minimum time to finish all jobs
 Text guide (Programmerall)
 Video guide (Happy Coding)
 Code example (lichuan199010)
Question 46: Maximum path quality of a graph
 Text guide (DBabichev)
 Video guide (Programming Live with Larry)
Question 47: Distribute repeating integers
 Text guide (Krammer Liu)
 Video guide (Happy Coding)
 Code example (alvin777)
4. Backtracking basics
In order to crack questions about backtracking, you’ll need to have a strong understanding of the algorithm, how it works, and when to use it.
4.1 What is backtracking?
Backtracking is a form of bruteforce problem solving, but with the ability to discard potential solutions early, before they are fully explored. It is an algorithmic paradigm for incrementally finding solutions to problems. As soon as a candidate will not result in the final complete solution being valid, the algorithm will “backtrack.” Therefore, backtracking can be applied when it is possible to test the validity of partial solutions.
Graph coloring provides us with an example of a backtracking algorithm in action. Suppose we have the following map of the continents and have a problem that requires us to give each continent a color such that no two adjacent continents have the same color, using the fewest colors possible. Such a condition is known as a constraint. We can test partial solutions against this constraint and discard them early if it’s clear the constraint won’t be met. This is the essence of backtracking.
Here, Europe and Asia should not be allowed to have the same color, and it's possible to color the map using only three colors.
It’s easier to view this problem as an undirected graph, like this:
Each node is a continent, and the edges between the nodes represent adjacent continents. Now our problem is coloring each node so that no two adjacent nodes have the same color, using the fewest colors (e.g. EU and AS should have different colors).
The solution starts by giving the American (AM) continent the first color – red. Europe (EU) is next, and since AM is already colored red, EU takes the next available color – blue. The algorithm prunes the search tree here by not considering red for EU, because all complete solutions that color AM and EU both red will be invalid. Therefore, the subsolution coloring both AM and EU red is also invalid.
Asia (AS) is next. AS can take red, since it is not connected to AM and the objective is to use the fewest colors. If no coloring of Africa (AF) and Australia and the Pacific Islands (AU) allows AS to be red, then the algorithm will backtrack to this point, and choose the next available color for AS. In that instance, blue will be skipped, since EU has been colored blue in this partial solution, so green might be next. However, in this example red is a valid color for AS with AF getting the color green and AU the color blue.
4.1.1 Use cases for backtracking
Backtracking can be applied to the following problems:
 Most Constraint Satisfaction Problems (CSP) like:
 The knight’s tour problem
 The n queens problem
 Solving sudoku
 Solving crosswords
 Graph coloring
 Most bruteforce algorithms
 String pattern matching
 To adapt a longest common subsequence (LCS) algorithm to print all the LCS in order
 Finding all subsets of a set
 Finding all paths from a source to a destination
4.1.2 Example implementation
Backtracking implementations are commonly recursive and similar to depthfirst search (DFS), except that only valid subsolutions are expanded in backtracking, whereas DFS will expand all the subsolutions of a node in the search space.
Our graph coloring results in the following implementation:
Here backtracking is just a wrapper around our recursive function. It prepares our solution colors to None for each node in the graph. The first node to color is then selected and if the recursive call succeeds, the solution can be returned.
The recursive call has the base case of current being None, meaning all the nodes have a valid color. Else, every possible color for the current node will be tested by adding it to the solution. If the complete solution is valid then the recursion can end, else backtracking needs to happen by setting the color back to None and the next color or node can be tested.
There are two helper functions that are specific to each problem being solved with backtracking. The first is select_unassigned to select the next node that needs to be colored. In this implementation, this helper function colors the nodes from 0 to n by finding the first open spot in solution. When no open spot is found, it means all the nodes are colored, so None is returned to stop the recursion. The second helper, get_domain_values, returns valid values for each node at a specific subsolution. For our example, this is where the algorithm should not consider red as a color for EU when AM is already red. This is done by looping through all the available colors and only yielding when a neighboring node does not already have the same color (the break together with the else is used in python to continue the outer loop).
The variable graph is an adjacency matrix where a graph[i][j] = 1 means that i and j are neighbors and AM is i = 0; EU is 2; AS is 3; AU is 4; and AF is 5.
Some heuristics can be used on the helper functions to improve performance. For the example above, after AM is red and EU is blue, the only value left for AF is green. But AF is last in the adjacency matrix, so it will be evaluated last. By evaluating AF earlier, the search space can be pruned earlier. Choosing the node with the least possible values is called the minimumremainingvalues (MRV) heuristic, and changes the implementation as follows:
Here, all the empty spots in solution are again found. But rather than stopping at the first empty spot, all valid colors for a spot are found with their count stored in dict in the first loop. If dict is empty, then all the nodes have a color and the recursion can stop, else the MRV is found using a heap.
Other heuristics are also possible. One is deciding the very first node to color using the degree heuristic to reduce the branching factor of future choices. The degree heuristic will choose the node with the largest number of constraints first – for our continents example, it is AF, since it has 4 edges while the other nodes have 3 or 2 edges. The degree heuristic can also be used to break a tie in the MRV heuristic.
Another heuristic is for getting the next color in get_domain_values. In our example, after AM is red and EU is green, it would be a bad idea to give AS blue since that will reduce the valid colors for AF (AF gets blue in the final solution). So trying red for AS first is a better idea by using the least constraining value heuristic.
The idea with heuristics is to reduce branching by selecting nodes that will fail as early as possible, but to go for a maximum search space depth by selecting values (colors) that will fail as late as possible. Together, these two tactics result in earlier success.
4.1.3 How backtracking compares to other algorithms
A bruteforce depthfirst search (DFS) is similar to backtracking. A bruteforce DFS will fully consider all the values (colors) for a node, but backtracking is able to prune its search space by only evaluating values that result in a valid subsolution.
An algorithm that does not need to backtrack when it hits a deadend is a greedy algorithm. A greedy algorithm only works for optimization problems with the greedy choice property to render the need for backtracking obsolete. But a greedy algorithm can only return a single solution, while backtracking can return all possible solutions.
Need a boost in your career as a software engineer?
If you want to improve your skills as an engineer or leader, tackle an issue at work, get promoted, or understand the next steps to take in your career, book a session with one of our software engineering coaches.
5. Backtracking cheat sheet
You can download the cheat sheet here.
5.1 Related algorithms and techniques
5.2 Cheat sheet explained
The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.
The cheat sheet is broken into time complexity and space complexity (the processing time and memory requirements for backtracking). Backtracking is related to several data structures, which are also included in the cheat sheet.
For more information about time and space requirements of different algorithms, read our complete guide to bigO notation and complexity analysis.
5.2.1 Time complexity
In our graph coloring example, the worst case will give each node its own color. Therefore, let m = V be the number of colors. This is also our branching factor at each node in the search space. Since every node needs to be assigned a color, the search space has a height of V to give a timecomplexity of O(m^V).
For all implementations, the get_domain_values will always determine the branching factor and the height will be the same size as solution. But for a problem like the n queens problem, solution is a 2D array with size n^2.
5.2.2 Space complexity
For the graph coloring problem, both solution and the implicit stack have a size of V to give a O(V) space complexity. The complexity will be bound to solution, and therefore gives the n queens problem a space complexity of O(n^2).
5.2.3 Related algorithms: dynamic programming and local search
Graph coloring can also be solved with other algorithmic paradigms, like dynamic programming. A dynamic programming solution will take O(2.4423^V) time and space. In general, dynamic programming offers a polynomial time complexity.
Another way of solving a CSP is to use a local search algorithm. For the n queens problem, a local search algorithm will randomly fill the board with all the queens and then iteratively move conflicting queens (to the least conflicting spot, for example). One such implementation uses the minconflicts heuristic to solve a 1 million queen problem in an average of 50 steps for a constant time complexity. However, local searches can get stuck at a local minimum.
6. How to prepare for a coding interview
6.1 Practice on your own
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only backtracking but also the rest of the relevant algorithms and data structures. You’ll also want to start working through lots of coding problems.
Check out the guides below for lists of questions organized by difficulty level, links to highquality answers, and cheat sheets.
Algorithm guides
 Depthfirst search
 Breadthfirst search
 Binary search
 Sorting
 Dynamic programming
 Greedy algorithm
 Divide and conquer
Data structure guides
 Arrays
 Strings
 Linked lists
 Stacks and Queues
 Trees
 Graphs
 Maps
 Heap
 Coding interview examples (with solutions)
To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems in the guides above on a piece of paper or google doc.
6.2 Practice with others
However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.
That’s why we recommend practicing with exinterviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1on1 with exinterviewers from leading tech companies. Learn more and start scheduling sessions today.