47 backtracking interview questions [easy, medium, hard]

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 sub-problems, 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 well-formed 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:

  1. Easy backtracking interview questions
  2. Medium backtracking interview questions
  3. Hard backtracking interview questions
  4. How to prepare for a coding interview

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

2. Medium backtracking interview questions

Here are some moderate-level 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
Question 3: Generate parentheses
Question 4: Permutations
Question 5: Subsets
Question 6: Word search
Question 7: Combination sum
Question 8: Word search II
Question 9: Palindrome partitioning
Question 10: Combination sum II
Question 11: Permutations II
Question 12: Subsets II
Question 13: Gray code
Question 14: Combinations
Question 15: Path sum II
Question 16: Combination sum III
Question 17: Matchsticks to square
Question 18: Restore IP addresses
Question 19: Increasing subsequences
Question 20: Beautiful arrangement
Question 21: Letter case permutation
Question 22: All paths from source to target
Question 23: Partition to K equal sum subsets
Question 24: Letter tile possibilities
Question 25: Path with maximum gold
Question 26: Maximum length of a concatenated string with unique characters
Question 27: Split array into Fibonacci sequence
Question 28: Split a string into the max number of unique substrings 
Question 29: Construct the lexicographically largest valid sequence
Question 30: Iterator for combination
Question 31: Splitting a string into descending consecutive values
Question 32: Closest dessert cost

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
Question 34: Sudoku solver
Question 35: Stickers to spell word
Question 36: Remove invalid parentheses
Question 37: Expression add operators
Question 38: N-Queens
Question 39: Unique paths III
Question 40: 24 Game
Question 41: N-Queens II
Question 42: Verbal arithmetic puzzle
Question 43: Longest subsequence repeated K times
Question 44: Number of squareful arrays
Question 45: Find minimum time to finish all jobs
Question 46: Maximum path quality of a graph
Question 47: Distribute repeating integers

4. How to prepare for a coding interview

4.1 Refresh your knowledge

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. Check out our guides for detailed explanations and useful cheat sheets.

Algorithms explained:

Data structure guides:

4.2 Practice on your own

Once you’re confident in all of these, you’ll want to start working through lots of coding problems.

For backtracking you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:

We also recommend working through our list of 73 data structure interview questions.

One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview.

It's also a good idea to work on a piece of paper or google doc, given that in the real interview you'll have to code on a whiteboard or virtual equivalent.

4.3 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 ex-interviewers 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 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.

cta_illustration arrow_left Browse FAANG ex-interviewers

Any questions about backtracking interview questions?

If you have any questions about backtracking or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!