DSA with Go — Part 18: Mastering Backtracking

Introduction

In the previous article, we learned about Prefix Sum, a powerful preprocessing technique that helps answer range queries efficiently.

Today, we’ll explore one of the most important algorithmic techniques used in coding interviews:

Backtracking

Many beginners find Backtracking difficult because it looks like “magic.”

In reality, it’s simply trying every possible choice, undoing that choice, and then trying the next one.

Backtracking builds directly on the recursion concepts we learned earlier.

If you understood recursion, you’re already halfway to understanding backtracking.

By the end of this article, you’ll understand:

• What Backtracking is
• How it differs from Recursion
• Decision Trees
• The Backtracking Template
• Generate all subsets
• Generate permutations
• Common interview problems
• Time complexity
• Real-world applications

Let’s begin.

What is Backtracking?

Backtracking is an algorithmic technique for exploring all possible solutions to a problem.

The idea is simple:

1. Make a choice.
2. Continue solving.
3. If the choice doesn’t work (or after recording a valid solution), undo it.
4. Try the next choice.

Think of it as exploring every path in a maze.

If one path reaches a dead end, you go back and try another path.

A Real-Life Analogy

Imagine you’re standing in a maze.

 Start
   |
   |
 Left ---- Right
   |
Forward

You choose one direction.

If you hit a dead end:

❌ Dead End

You return to the previous junction and try another direction.

This process of returning is called backtracking.

Backtracking vs Recursion

Many people think they’re the same.

They’re not.

Think of Backtracking as Recursion + Undoing Changes.

Decision Tree

Suppose we want to generate all subsets of:

[1,2]

For every element, we have two choices:

• Include it
• Exclude it

Decision tree:

           []
          /  \
       [1]   []
      /  \   / \
 [1,2] [1] [2] []

Every path represents one possible answer.

The Backtracking Template

Almost every backtracking problem follows the same structure.

func backtrack(...) {

    if solutionFound {
        saveAnswer()
        return
    }

    for every possible choice {
        makeChoice()
        backtrack(...)
        undoChoice()
    }
}

Notice the important step:

Undo Choice

Without undoing, future paths become incorrect.

Example 1: Generate All Subsets

Given:

[1,2,3]

Output:

[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

Every element has two choices:

• Pick it
• Skip it

Go Implementation

func subsets(nums []int) [][]int {

    var result [][]int
    var current []int
    var dfs func(index int)

    dfs = func(index int) {
      if index == len(nums) {
         temp := append([]int{}, current...)
         result = append(result, temp)
         return
      }

      // Include
      current = append(current, nums[index])
      dfs(index + 1)

      // Backtrack
      current = current[:len(current)-1]

      // Exclude
      dfs(index + 1)
   }

 dfs(0)
 return result
}

Why Do We Copy the Slice?

Notice:

temp := append([]int{}, current...)

Why not:

result = append(result, current)

Because slices share the same underlying array.

Without copying, every result would eventually contain the same values.

This is one of the most common mistakes in Go backtracking problems.

Example 2: Generate All Permutations

Given:

[1,2,3]

Output:

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Here, every unused number becomes the next choice.

Go Implementation

func permute(nums []int) [][]int {

    var result [][]int
    var current []int
    used := make([]bool, len(nums))
    var dfs func()

    dfs = func() {
        if len(current) == len(nums) {
          temp := append([]int{}, current...)
          result = append(result, temp)
          return
        }

        for i := 0; i < len(nums); i++ {
           if used[i] {
           continue
           }

        used[i] = true
        current = append(current, nums[i])
        dfs()
        current = current[:len(current)-1]
        used[i] = false
       }
    }
 dfs()
 return result
}

Notice how we undo both:

• The current slice
• The used array

That’s backtracking.

Understanding “Undo”

Suppose:

Current
[1]

Choose:

2

Now:

[1,2]

After exploring every possibility beginning with [1,2], we must return to:

[1]

Otherwise, the next branch starts with incorrect data.

This “returning to the previous state” is the heart of backtracking.

Common Interview Problems

Backtracking is used in many classic interview questions:

• Generate Subsets
• Generate Permutations
• Combination Sum
• Letter Combinations of a Phone Number
• N-Queens
• Sudoku Solver
• Word Search
• Restore IP Addresses
• Palindrome Partitioning

Although these problems look different, they all use the same underlying pattern.

Time Complexity

Backtracking often explores every possible solution.

Examples:

These algorithms are expensive, but they are often the only practical approach for combinatorial problems.

How to Recognize Backtracking Problems

Ask yourself:

• Do I need to generate all possible answers?
• Am I making a sequence of choices?
• Do I need to undo previous decisions?
• Is recursion naturally involved?

If the answer is yes, backtracking is likely the right approach.

Real-World Applications

Sudoku Solvers

Try a number.

If it violates the rules:

Undo it.

Try another number.

Maze Solvers

Explore one path.

If blocked:

Return and try another path.

Route Planning

Explore different routes and eliminate invalid ones.

Password Generation

Generate all valid combinations under certain rules.

Puzzle Solvers

Games like crossword generators, chess engines, and logic puzzles often rely on backtracking to explore possible moves.

How This Helps in Backend Engineering

You may not write Sudoku solvers in a backend service, but backtracking teaches an important skill:

Systematically exploring a search space while keeping state consistent.

This mindset is useful in:

• Rule engines
• Workflow generation
• Configuration validation
• Scheduling systems
• Resource allocation

Many optimization problems begin with a backtracking solution before being improved with more advanced techniques.

Common Mistakes

Forgetting to Undo

The biggest mistake.

Always undo every change before exploring the next choice.

Not Copying Slices

In Go:

temp := append([]int{}, current...)

Always copy before storing the result.

Incorrect Base Case

Without a correct stopping condition, recursion never ends or produces incomplete results.

Modifying Shared State

Be careful when working with slices, maps, or pointers.

Always restore shared state before returning.

Key Takeaways

• Backtracking explores every possible solution.
• It is built on recursion.
• Every choice must eventually be undone.
• The same template solves many interview problems.
• Copy slices before saving results in Go.
• Backtracking is commonly used for combinations, permutations, puzzles, and search problems.

See you in Part 19.