cf.completefrontend
RECURSION & BACKTRACKING · CORE

Backtracking

Build an answer one choice at a time, and undo the last choice when it leads nowhere so you can try the next one.

Time O(k^n × n)Space O(n)12 practice problemsStep-through picture

The idea

Some problems ask for every answer that follows a rule, such as every password of length 3 with no letter twice in a row. You can't find those answers with one formula. You have to try choices.

Backtracking tries them in an orderly way. It keeps a path: the choices made so far. It adds one choice, then goes deeper to add the next. When the path is complete, it saves a copy. When a choice breaks the rule, it skips that choice. After going deeper, it removes the last choice again, which is the step back that gives the method its name, and tries the next choice in the same spot.

This visits every possible answer exactly once, and it never builds a path that already broke the rule. That second part is what makes it faster than listing every possible string and checking each one at the end.

An everyday example

Walking through a maze with a ball of string

You enter a maze holding a ball of string, and you unroll it as you walk. At every fork you take the first path you haven't tried. If you hit a dead end, you walk back along the string, rolling it up, to the last fork, and try the next path there. When you reach an exit, you write down the route your string shows. Because you always roll the string back up, the string shows exactly the route from the entrance to where you stand.

How the example maps to the code
In the exampleIn the code
The string from the entrance to where you standThe path array
Taking a new path at a forkpath.push(choice) then explore()
Rolling the string back up after a dead endpath.pop()
A path you can see is blocked, so you don't walk incontinue when a choice breaks the rule
Writing down the route at an exitresults.push(path.join(""))

From the slow way to backtracking

  1. Say you want every string of length n made from the letters u, v, and w, with no letter twice in a row. The obvious way is to list every string of length n first, then throw away the bad ones. With 3 letters that is 3^n strings: 59,049 of them for n = 10, and each one takes n steps to build and check.
  2. Most of that work is wasted. Once a string starts with uu, nothing you add after it can fix it. Yet the obvious way still builds all 6,561 strings of length 10 that begin with uu, one by one, only to throw each away. The useful fact is this: a broken start stays broken, so the rule can be checked on a partial string, not only on a finished one.
  3. So build the string one letter at a time, and check the rule each time you add a letter. If a letter breaks the rule, don't add it, and never look at anything that would grow from it. This turns the flat list of strings into a tree of choices: the root is the empty string, each child adds one letter, and one skipped letter cuts off a whole branch of the tree.
  4. Walking that tree needs a memory of where you are. Keep one array, path, for the letters chosen so far. Going down a branch is path.push(choice). Coming back up is path.pop(), which puts path back the way it was, so the next letter at the same spot starts from the same place. A recursive function, explore, handles one level of the tree per call. That loop of push, explore, pop, with a skip for broken choices, is backtracking.

How it works

  1. Keep a path array with the choices made so far, and a results array for the finished answers.
  2. Write a recursive function, explore, that tries to extend the path by one more choice.
  3. In explore, first check if the path is complete. If it is, save a copy into results and return.
  4. Otherwise loop over every choice. Skip any choice that would break the rule right away.
  5. For a valid choice, add it with path.push(choice) and call explore() to fill the next spot.
  6. When that call returns, undo the choice with path.pop(), so the next loop step starts from the same path.
  7. Start with one call, explore(), on an empty path, and return results at the end.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function noRepeatStrings(choices, length) {
  2. const results = [];
  3. const path = [];
  4. function explore() {
  5. if (path.length === length) {
  6. results.push(path.join(""));
  7. return;
  8. }
  9. for (const choice of choices) {
  10. if (path[path.length - 1] === choice) continue;
  11. path.push(choice);
  12. explore();
  13. path.pop();
  14. }
  15. }
  16. explore();
  17. return results;
  18. }

How fast it is

TimeO(k^n × n)
Extra memoryO(n)

With k choices and length n, there can be up to k^n paths, and each saved answer takes n steps to copy. Apart from the output, the only memory is path and the chain of calls, both at most n deep.

  • Best caseO(1)

    The rule cuts everything at once, such as choices = ["a"] with length = 3: a is pushed, the next spot skips a, and the search ends after 2 calls with no answers.

  • Average caseO(n × k × (k-1)^(n-1))

    With this rule, each spot after the first has k - 1 allowed letters, so there are k × (k-1)^(n-1) answers, each copied in n steps. For k = 3 and n = 10 the search makes 3,070 calls and saves 1,536 strings.

  • Worst caseO(k^n × n)

    A rule that never rejects anything: every one of the k^n strings is built and copied. This is the page's general bound.

Common mistakes

  • Saving path itself with results.push(path). Every saved entry is the same array, which ends up empty. Save a copy: [...path] or path.join("").
  • Forgetting path.pop() after the deeper call. The path keeps growing, and later answers contain old choices.
  • Checking the rule only when the path is complete. The answer is right but the search builds many paths that were already broken. Check as early as you can.
  • Using backtracking when the question only wants a count of a huge number of answers. The count can be found much faster with dynamic programming.

When to use it

Look for these clues in a problem:

  • The question asks for all answers, not just one number: "list every", "generate all", "return every way".
  • Each answer is built from a series of small choices, such as one letter, one item, or one cell at a time.
  • The input is small, often 10 to 20 items, because the number of answers can grow very fast.
  • There is a rule that lets you reject a partial answer early, before it's complete.

Check yourself

Answer each one in your head first, then open it.

Why can one shared path array serve every call?

Because each call undoes exactly what it did: one push before the deeper call and one pop after it. So when control returns to a loop, path is the same as before that loop step.

With choices = ["u", "v", "w"] and length = 2, which strings are never built?

uu, vv, and ww. Each is cut at its second letter by the continue, which is why the trace has 3 skip rows.

What happens if you delete the path.pop() line?

path keeps growing past length, so path.length === length is never true again and the recursion goes deeper until the engine throws a RangeError for the call stack.

Why must the time be at least the number of answers times n?

Every answer has n letters, and each one is copied into results with path.join(""). Just writing the output takes that long.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 12 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Backtracking keeps one rule. When explore is called, path holds a valid start of an answer, and when that call returns, path is exactly as it was at the call. The first part holds because a choice is only pushed after it passes the check. The second part holds because every push is matched by one pop right after the deeper call, and the deeper calls keep the same rule.

Every valid answer is found. Take any valid string, such as "wu". At the first spot the loop tries w, which passes the check, so the search goes down that branch. At the second spot it tries u, which passes too, so "wu" is saved. A choice is only skipped when it already breaks the rule, and then every string that would grow from it breaks the rule too, so no valid string is ever lost.

No answer is saved twice, and the search always ends. Two different strings differ at some first position, so they live in different branches of the tree and are reached by different loop steps. The tree has at most length levels, and each level loops over a fixed list of choices, so there are only a limited number of calls. When the top-level loop ends, every branch has been tried.

Going deeper

3 more ideas

Why the undo step keeps everything correct

Every call to explore must leave path exactly as it found it. A call adds one item, goes deeper, and removes the same item. The deeper calls follow the same rule, so when control returns to a loop, path holds the same choices as before the loop step. That is why one shared array is enough for the whole search.

Why skipping early saves so much work

Without the rule, 2 letters and length 3 give 2 × 2 × 2 = 8 strings to check. The skip on the second letter cuts every branch that starts with aa or bb before it grows. With 3 letters and length 10 the difference is 59,049 strings against 1,536. Rejecting a bad partial answer removes every answer that would grow from it.

How long it takes

Backtracking is slow by nature: the time is about the number of answers times the length of each one, because each answer is built and copied. That is fine when the input is small. When a problem only asks how many answers exist, or for the best one, other methods such as dynamic programming are often faster.

Work it by hand

Every step in a table, with why

Every 2-letter string from three letters, with no letter twice in a row. Each row is one turn of the for loop, at whichever depth the search is.

choices = ["u", "v", "w"], length = 2

Steppath beforechoicepath afterWhat happensWhy
1[]u[u]push, go deeperpath is empty, so there is no last letter to clash with. Push u and call explore() to fill the second spot.
2[u]u[u]skipu equals the last letter of path, so continue skips it. Nothing that starts with uu is ever built.
3[u]v[u, v]save "uv"path.length is now 2, so the deeper call saves "uv" and returns at once. Then path.pop() puts path back to [u].
4[u]w[u, w]save "uw"Same spot, next choice. Save "uw" and pop back to [u]. The loop at this depth is done, so this call returns and its caller pops u.
5[]v[v]push, go deeperBack at the top level with an empty path. Now v is tried as the first letter.
6[v]u[v, u]save "vu"A letter may appear again later, just not right after itself, so u after v is fine.
7[v]v[v]skipv would repeat the last letter, so it is skipped.
8[v]w[v, w]save "vw"Save "vw", pop to [v], and return, so the top level pops v.
9[]w[w]push, go deeperThe last first letter to try.
10[w]u[w, u]save "wu"Save "wu" and pop back to [w].
11[w]v[w, v]save "wv"Save "wv" and pop back to [w].
12[w]w[w]skipHere the skip is the very last loop step. The inner loop ends, w is popped, and the top-level loop ends too.

It returns ["uv", "uw", "vu", "vw", "wu", "wv"]: 6 of the 3 × 3 = 9 possible strings. The 3 skipped rows are the strings uu, vv, and ww, which were never built. The search ends when the top-level loop has tried all three first letters.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
BacktrackingO(n · 2^n)O(n)You need every valid string. With 3 letters the rule leaves 3 × 2^(n-1) answers, and the search builds only those plus a few dead ends.
Build every string, then filterO(n · 3^n)O(n)Only when the rule can't be checked until the string is complete. Otherwise it builds every uu... string just to throw it away.
Count with a formula or dynamic programmingO(n)O(1)The question only asks how many answers there are. Multiply k by k - 1 for each later spot instead of listing anything.

Extra memory: O(n) besides the output: path holds at most length letters, and the call chain is at most length + 1 calls deep. The results array grows with the number of answers, which can be far larger.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Backtracking and the other approaches, on a scale where each line up is 10 times more steps.
  • Backtracking O(n · 2^n)
  • Build every string, then filter O(n · 3^n)
  • Count with a formula or dynamic programming O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Backtracking10,240more than a quadrillionmore than a quadrillion
Build every string, then filter590,490more than a quadrillionmore than a quadrillion
Count with a formula or dynamic programming101,0001 million

Inputs that need care

5 tricky inputs
length = 0
path.length === length is true on the very first call, so it saves path.join(""), the empty string, and returns [""]. That is correct: there is exactly one string of length 0.
choices = [], length = 2
The for loop never runs, so nothing is saved and it returns []. No special check is needed.
One letter, choices = ["a"], length = 3
The second spot can only try a, which repeats the last letter, so the search dead-ends and returns [].
Repeated letters, choices = ["u", "u", "v"], length = 2
Both copies of u are tried as the first letter, so the result is ["uv", "uv", "vu", "vu"]. Remove repeats first with [...new Set(choices)] if each answer should appear once.
A big output: 10 letters and length = 8
There are 10 × 9^7 = 47,829,690 valid strings. The code is correct but the output alone won't fit in a browser tab. If only the count is needed, compute k × (k-1)^(n-1) instead of listing.

Variations and follow-ups

Twists interviewers add

Stop at the first answer

Make explore return true when it finds a complete answer, and return at once when a deeper call returns true. The search ends as soon as one answer exists. Puzzle solvers use this, since they only need one solution.

Count instead of collect

Replace results.push(...) with count++. This saves memory, but the time is still the number of answers. When only the count matters, look for a formula or dynamic programming, which can count without visiting each answer.

Branch and bound

When you want the best answer by some score, keep the best score found so far. Before going deeper, estimate the best score this branch could still reach, and skip the branch if it can't beat the current best. This is backtracking with a smarter skip rule.

An explicit stack instead of recursion

Each call can be stored as a small record (how long path is, and which choice to try next) on your own stack array. The search order stays the same, and very deep searches no longer depend on the engine's call stack limit.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from words like "generate all", "list every", or "return all valid", together with small limits such as n <= 10. A small limit is a hint that an exponential search is expected.
  • Explain it as three moves: choose (path.push), explore (the recursive call), and un-choose (path.pop). Then say where the rule check sits and why it sits before the push, not at the end.
  • Test by hand with length = 0, a single letter, and a tiny case where one skip happens, like the trace above. Most bugs are a missing pop or saving path without a copy.
  • Expect "what is the time?". Answer with the number of tree nodes times the cost of copying an answer, and point out that the output size is a floor no method can beat when every answer must be listed.
  • Expect "can you make it faster?". The honest answer: move the rule check earlier so more branches are cut, or, if only a count or a best value is needed, switch to dynamic programming.

Where frontend code uses it

The same idea in real UI code
  • JavaScript's RegExp engine in V8 is a backtracking engine: when a part of a pattern fails, it steps back and tries another way to match. Patterns like (a+)+$ can make it try a huge number of ways, which is how a bad regular expression can freeze a page.
  • Design systems often test every combination of a component's props (size, variant, state). Generating those combinations is a small backtracking search.
  • Form builders and checkout flows with dependent options (a size that only exists for some colors) can list valid choices by building one option at a time and skipping invalid ones.

Related algorithms