Practical backtracking

For the longest time, I despised backtracking problems.
They always felt too abstract — filled with confusing conditions, endless recursion, and a constant sense that I didn’t really know what I was doing.

That changed when I started visualizing the process — literally drawing trees, branches, and dead ends. Suddenly, things started clicking.
I could see how the algorithm explored and backtracked, and how constraints shaped the paths.

In this post, I want to approach backtracking differently:
I’ll take a typical backtracking problem, break it down into its constraints, and solve it step by step — with visual diagrams to aid our thinking.

You can follow along with pen and paper, or use a tool like Excalidraw (my personal favorite) to sketch as you go.

My goal is to help you see that backtracking doesn’t have to be magical or intimidating — it’s just structured trial and error, and with the right mindset, it can even feel… elegant.

Problem at hand

Going to choose a problem from Leetcode, it will be fairly easy for folks who understand backtracking, but pretty sure it will be challenging for people who struggle with backtracking.

Generate binary strings without adjacent zeros

You are given a positive integer n.
A binary string x is valid if all substrings of x of length 2 contain at least one "1".
Return all valid strings with length n, in any order.

Example 1:
Input: n = 3
Output: ["010","011","101","110","111"]
Explanation:
The valid strings of length 3 are: "010", "011", "101", "110", and "111".
Example 2:
Input: n = 1
Output: ["0","1"]
Explanation:
The valid strings of length 1 are: "0" and "1".

Constraints:
1 <= n <= 18

Understanding the problem

For any given n, say n = 3, a binary string is valid if the substring of length 2 contains at least one "1".

So a substring is a slice of the string, here if the string is 010 then all substrings of length 2 would be

01
10

We sliced off the main string to get two substrings, let's try with a longer string 1011

10
01
11

So as per the problem statement if the substring contains at least one "1", that means, there could be no two adjacent zeros as well, so for n = 3, 010 is valid string, and we want to find all such valid strings for n=3, that satisfy this criteria.

Solving the problem

Solving this problem with recursion seems like a obvious choice, why ?
Its easier to generate values that take into account the previous values

Equivalent code for this

function backtrack(str) {
  backtrack(str+'0');
  backtrack(str+'1');
}

backtrack('');

So here we understand following conditions

1. Binary strings only have 0 or 1.
2. There can be no 2 adjacent 0s.
3. Collect all valid strings that follow above criteria of given length n.

Above code is not quite right though, if you see that there is no return statement, also the backtrack function is going to keep adding 0 to the string infinitely, so its going to go into a infinite loop, '' -> '0' -> '00', we are never hitting the "1" branch. Let's fix that with some conditions / base conditions

backtrack("")
├── backtrack("0")
│   └── backtrack("00")
│       └── backtrack("000")
│           └── ... ← NO END, GOES ON INFINITELY
└── backtrack("1") ← NEVER REACHED

function validBinaryStrings(n) {
 function backtrack(str) {
  if (str.length === n) {
      return; 
  }
  backtrack(str+'0');
  backtrack(str+'1');
}

backtrack('');

}

So above condition makes sure we exit the infinite loop or rather we don't stay stuck, condition is simple, we want to exit the function call if the length of string is n, this is as per one of the condition.

But we are not storing the results anywhere, we need to store the final results, lets put things in an array.

function validBinaryStrings(n) {
 const results = [];
 function backtrack(str) {
  if (str.length === n) {
     results.push(str); // push all generated strings in array 
     return; 
  }
  backtrack(str+'0');
  backtrack(str+'1');
}

backtrack('');
return results;
}

console.log(validBinaryStrings(3));

So above function will generate all binary strings where n = 3, if you run this in browser console or some online JS code editor, you will get this

['000', '001', '010', '011', '100', '101', '110', '111']

So are able to generate all binary strings of length n, but we are violating condition 2. no adjacent 0s.

At this point we can say we are hitting all the paths of the recursion tree and collecting all its leaf

To fix that we can check if the last character of the string is a zero, if not we add 0 to its end, if it is, we skip it

function validBinaryStrings(n) {
 const results = [];
 function backtrack(str) {
  if (str.length === n) {
     results.push(str); // push all generated strings in array 
     return; 
  }
  if(str[str.length - 1] !== '0') {
    backtrack(str+'0');
  }
  backtrack(str+'1');
}

backtrack('');
return results;
}

console.log(validBinaryStrings(3));

Boom! That's it, we have the final solution, key takeaway is to draw out the tree to understand if the generation works, what paths to prune in case we don't want all the leaf of the tree, usually we want to collect the leaf, but if that is not the case we can add some more logic to collect other states.

Key takeaway: Sketching out a decision tree / recursion tree adds more clarity while solving backtracking problems, you can use pen and paper or Excalidraw, its up to you, this should serve as a good technique for solving backtracking problems.

Let me know your thoughts and views about this article. Thank you !