DFS to Backtracking — Understanding the Intuition Through Four Problems

Backtracking is one of those algorithms that often feels mysterious when we first encounter it. We memorize a template, learn where to add an element, where to remove it, and somehow it works. But why does it work? More importantly, where does backtracking actually come from?

While revising Depth First Search (DFS), I realized that backtracking isn’t really a separate algorithm at all. It is simply a natural extension of recursive DFS.

In this article, we’ll start with a simple DFS problem and gradually evolve it into backtracking. Instead of memorizing templates, we’ll derive the intuition step by step through four problems:

• Path Sum I
• Path Sum II
• All Paths from Source to Target
• Subsets
• Permutations

By the end of the article, you’ll hopefully stop thinking of backtracking as “another algorithm” and start recognizing it as DFS where we carefully restore the recursive state before exploring another choice.

Let’s begin.

Path Sum I — A Simple DFS Problem

Problem Statement

Given the root of a binary tree and an integer targetSum, determine whether the tree has at least one root-to-leaf path whose node values add up to targetSum.

Notice the wording carefully.

We are not asked to find every valid path.

We only care whether at least one such path exists.

The moment we find one valid path, we can immediately stop searching.

Thinking Through the Problem

Let’s begin at the root.

If the current node contributes root.val to the path sum, then the remaining nodes only need to contribute:

remainingSum = targetSum - root.val

Now the problem becomes:

Does the left subtree contain a root-to-leaf path whose sum is remainingSum?

or

Does the right subtree contain a root-to-leaf path whose sum is remainingSum?

Notice something interesting.

We’re asking exactly the same question on a smaller tree.

That’s usually a strong hint that recursion might be a natural solution.

Recursive State

At every recursive call, we only need two pieces of information:

• The current node.
• The remaining sum we still need to achieve.

(node, remainingSum)

Nothing else needs to be remembered.

The Recursive Solution

If the current node is null, we've reached the end of a path without finding a valid answer.

If the current node is a leaf, we simply check whether its value equals the remaining sum.

Otherwise, subtract the current node’s value from the remaining sum and recursively search both subtrees.

If either subtree returns true, we have found a valid root-to-leaf path.

This is a classic recursive DFS.

We’re simply traversing the tree while carrying one extra piece of information (remainingSum) along the recursive calls.

Complete Solution

class Solution {

    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {

        if (root == null) return false

        if (root.left == null &&
            root.right == null &&
            root.`val` == targetSum
        ) {
            return true
        }

        val remainingSum = targetSum - root.`val`

        return hasPathSum(root.left, remainingSum) ||
                hasPathSum(root.right, remainingSum)
    }
}

Time Complexity

Every node is visited at most once.

If the tree contains N nodes,

Time Complexity = O(N)

Space Complexity

The extra space comes entirely from the recursion stack.

At any point, the recursion stack only contains the nodes on the current root-to-current-node path.

For a balanced binary tree, the height is approximately log N, giving:

O(log N)

For a completely skewed tree, the height becomes N, giving:

O(N)

Notice that we never store all possible paths simultaneously.

The recursion only remembers the current path it is exploring.

So far, this is straightforward DFS.

But what happens if the problem changes just a little?

Path Sum II — When DFS Naturally Becomes Backtracking

Let’s slightly modify the previous problem.

Problem Statement

Instead of simply checking whether at least one valid root-to-leaf path exists, we now need to return every root-to-leaf path whose sum equals targetSum.

At first glance, this doesn’t look like a huge change.

After all, we’re still traversing the same binary tree using DFS.

But this small change completely changes what our recursive function needs to remember.

Why Path Sum I Is No Longer Enough

In Path Sum I, our recursive state was:

(node, remainingSum)

That was sufficient because we only needed a yes/no answer.

The moment we found a valid path, we returned true and stopped searching.

There was nothing else worth remembering.

Path Sum II is different.

When we reach a valid leaf node, we aren’t just interested in the sum.

We also need to know which nodes formed that path.

That means our recursive state must now include one more piece of information:

(node, remainingSum, path)

where path stores the nodes from the root to the current node.

Building the Path

As we visit each node, we simply append it to our current path.

Suppose we’re exploring the tree below.

        5
       /
      4
     /
    11

As recursion progresses, our path gradually grows.

Visit 5
path = [5]
Visit 4
path = [5,4]
Visit 11
path = [5,4,11]

Nothing surprising so far.

When Should We Record the Path?

Exactly like Path Sum I, we only care about root-to-leaf paths.

So reaching an internal node isn’t enough.

When we arrive at a leaf node, we ask two questions:

• Is this a leaf?
• Does the remaining sum equal the current node’s value?

If both conditions are true, we’ve found one valid path.

Since the path will continue changing as recursion explores other branches, we must store a copy of it.

result.add(path.toList())

Notice the copy.

If we stored the same mutable list, every path inside our result would continue changing as recursion proceeds.

A Tempting (But Inefficient) Solution

At this point, many of us think of a simple solution.

Instead of sharing one list, why not create a new copy for every recursive call?

Left child receives a new copy.
Right child receives another new copy

This certainly works.

But now we’re repeatedly creating new lists during every recursive call.

Can we do better?

A Better Question

Suppose we use one shared list instead.

Is there any point during recursion where that becomes unsafe?

Let’s think carefully.

Imagine we’re currently exploring the left subtree.

While we’re inside the left subtree, does the right subtree need to modify the list?

No.

The right subtree won’t even begin executing until the left subtree has completely finished.

That observation changes everything.

Instead of creating a fresh list for every recursive call, we can reuse the same list throughout the entire traversal.

We only need to ensure that the list is restored to its previous state before exploring another branch.

The Birth of Backtracking

Every recursive call now follows the same sequence.

Step 1 — Choose

We visit the current node.

path.add(root.`val`)

Step 2 — Explore

Recursively search the left subtree.

Recursively search the right subtree.

During this time, the current node belongs to our path.

Step 3 — Undo

Once both recursive calls finish, we’re done exploring every path that passes through this node.

Before returning to the parent, we simply remove the current node.

path.removeAt(path.lastIndex)

Now the shared list is exactly as it was before we visited this node.

The parent can safely explore another branch without any leftover state from the previous one.

This single undo operation is what transforms ordinary DFS into backtracking.

We aren’t just traversing the tree anymore.

We’re carefully restoring the recursive state after every choice.

Complete Solution

class Solution {

    fun pathSum(root: TreeNode?, targetSum: Int): List<List<Int>> {

        val result = mutableListOf<List<Int>>()
        val path = mutableListOf<Int>()

        fun dfs(node: TreeNode?, remainingSum: Int) {

            if (node == null) return

            path.add(node.`val`)

            if (node.left == null &&
                node.right == null &&
                node.`val` == remainingSum
            ) {
                result.add(path.toList())
            } else {

                val newRemainingSum = remainingSum - node.`val`

                dfs(node.left, newRemainingSum)
                dfs(node.right, newRemainingSum)
            }

            path.removeAt(path.lastIndex)
        }

        dfs(root, targetSum)

        return result
    }
}

Time Complexity

The DFS traversal still visits every node exactly once.

That contributes:

O(N)

where N is the number of nodes.

Whenever we find a valid path, we create a copy of it before storing it in the result.

Suppose:

• K = number of valid paths.
• H = height of the tree.

Copying one path takes at most O(H) time.

Therefore,

Time Complexity = O(N + K × H)

If no valid paths exist, the second term simply disappears.

Space Complexity

Ignoring the output itself, the extra space comes from two places.

The recursion stack stores one recursive call per level of the tree.

The shared path list also stores one node per level.

Both grow only as deep as the height of the tree.

So the auxiliary space is:

O(H)

For a balanced tree:

O(log N)

For a completely skewed tree:

O(N)

The result list is not counted as auxiliary space because it is part of the required output.

At this point, we have discovered something interesting.

Backtracking isn’t a completely different algorithm.

It simply emerged because one piece of our recursive state (path) became mutable, and we had to restore it before exploring another branch.

Can this same pattern appear outside binary trees?

Absolutely.

In fact, if you’ve read my article on All Paths from Source to Target, you’ve already seen backtracking in action without us explicitly calling it that.

All Paths from Source to Target — The Same Pattern in a Graph

If you’ve read my previous article on All Paths from Source to Target, you may already be familiar with this problem.

***[Link to my DFS Part II article]***

Instead of a binary tree, we’re now given a Directed Acyclic Graph (DAG), and our goal is to return every possible path from node 0 to node n - 1.

The complete solution is covered in the earlier article, so let’s focus only on what changes from Path Sum II.

What’s Different?

In Path Sum II, our recursive state was:

(node, remainingSum, path)

The path represented the nodes from the root to the current node.

In All Paths from Source to Target, we no longer care about sums.

Our recursive state becomes:

(node, path)

Here, path represents the nodes from the source (node 0) to the current node.

Notice what happened.

We removed one piece of recursive state (remainingSum), but the backtracking pattern remained exactly the same.

The Backtracking Pattern Hasn’t Changed

For every recursive call, we still follow the exact same sequence.

Choose

Visit the current node.

path.add(node)

Explore

Instead of exploring a left and right child, we now explore every outgoing edge.

for (neighbor in graph[node]) {
    dfs(neighbor)
}

The graph decides how many recursive calls are made.

A node may have one neighbor, two neighbors, or many neighbors.

Undo

Once every neighbor has been explored, we restore the shared path.

path.removeAt(path.lastIndex)

That’s it.

The backtracking itself hasn’t changed at all.

A Subtle Difference

Although the code looks almost identical, there is one conceptual difference between these two problems.

In Path Sum II, we are traversing an existing binary tree.

The recursive calls are determined by the tree structure.

dfs(left)
dfs(right)

In All Paths from Source to Target, we are traversing an existing graph.

The recursive calls are determined by the graph’s adjacency list.

for every neighbor

In both cases, we are simply following an existing structure.

We aren’t creating any new choices ourselves.

The input tells us exactly where we are allowed to go next.

Why Don’t We Need a Visited Array?

A common question is:

“We’re doing DFS on a graph. Why don’t we need a visited array?”

The answer lies in one important word from the problem statement.

The graph is a Directed Acyclic Graph (DAG).

Since there are no cycles, recursion can never revisit the same node along the current path and get stuck in an infinite loop.

Interestingly, using a global visited array would actually produce the wrong answer.

Suppose node 3 can be reached through two different paths.

0 → 1 → 3
0 → 2 → 3

Both are valid paths that must appear in the answer.

If we permanently marked node 3 as visited after exploring the first path, we would incorrectly skip the second one.

The absence of cycles guarantees that recursion will terminate naturally, while allowing us to revisit the same node through different paths whenever necessary.

Have We Really Learned Backtracking Yet?

At this point, we’ve seen backtracking in both trees and graphs.

But notice something.

In both problems, the input already contained a structure for us to traverse.

The tree existed.

The graph existed.

Our job was simply to follow it.

The next problem changes that completely.

For the first time, there is no tree and no graph.

We will create the decision tree ourselves.

And that’s where backtracking truly starts to reveal its full power.

Subsets — Building the Decision Tree Yourself

Until now, every problem gave us something to traverse.

• Path Sum I gave us a binary tree.
• Path Sum II gave us a binary tree.
• All Paths from Source to Target gave us a graph.

In all three problems, the recursive calls were determined by the input itself.

Subsets is different.

There is no tree.

There is no graph.

There are only decisions.

Problem Statement

Given an integer array nums containing unique elements, return all possible subsets (the power set).

The solution must not contain duplicate subsets.

The order of the subsets does not matter.

Let’s Forget Recursion for a Moment

Suppose I give you:

nums = [1,2,3]

Before thinking about code, ask yourself one simple question.

How many choices does each element have?

Take the first element.

1

Can we include it?

Yes.

Can we exclude it?

Also yes.

The same is true for every other element.

Each element has exactly two choices.

Include it.

Exclude it.

Instead of traversing an existing tree, we can now imagine a decision tree.

                    [ ]
                  /     \
           Include 1   Exclude 1
             /   \        /   \
            +2   -2     +2    -2

For every element, recursion simply asks:

Should I include this element in my subset?

That is the entire problem.

The Recursive State

In the previous problems, our recursive state always included a node.

This time, there is no node.

Instead, every recursive call needs to know two things.

(index, subset)

• index tells us which element we are currently making a decision about.
• subset stores the partial subset we have built so far.

Notice that subset no longer represents a path in a tree or graph.

It now represents a partial solution.

This is an important mental shift.

Backtracking is not about paths.

It is about gradually building a solution one choice at a time.

When Is a Subset Complete?

This is the question that determines the base case.

Many beginners instinctively try to record the subset every time they include an element.

Let’s test that idea.

Suppose:

nums = [1,2]

If we record the subset as soon as we include 1, we get:

[1]

But have we decided what to do with 2 yet?

Not at all.

Maybe we’ll include it.

Maybe we’ll exclude it.

The subset isn’t complete because one decision is still pending.

A subset becomes complete only after we’ve made a decision about every element.

That gives us our base case.

if (index == nums.size) {
    result.add(subset.toList())
    return
}

Reaching the end of the array is equivalent to reaching a leaf in the decision tree.

Every decision has been made.

The current subset is complete.

Deriving the Recursive Calls

Suppose we’re here.

nums = [1,2,3]

index = 1

subset = [1]

What does this state tell us?

We’ve already decided to include 1.

Now we’re making a decision about 2.

There are exactly two possibilities.

Choice 1 — Include 2

subset.add(nums[index])
dfs(index + 1)
subset.removeAt(subset.lastIndex)

Notice the undo step.

We restore the subset before trying the second choice.

Choice 2 — Exclude 2

Excluding an element doesn’t modify the subset at all.

So after the undo, we simply continue.

dfs(index + 1)

This is an interesting observation.

Only the branch that changes the recursive state requires an undo.

The exclude branch leaves the subset untouched, so there is nothing to restore.

The Complete Backtracking Pattern

Every recursive call follows the same sequence.

Choose
    Include nums[index]
Explore
    Solve the remaining problem
Undo
    Remove nums[index]
Explore Again
    Solve the problem after excluding nums[index]

The algorithm looks different from the previous problems because there is no tree to traverse.

But if you look closely, the pattern is identical.

We are still choosing.

We are still exploring.

We are still restoring the recursive state before exploring another choice.

Complete Solution

Time Complexity

Let’s derive it together.

Suppose there are N elements.

Each element has exactly two choices.

Include
Exclude

So the total number of subsets becomes:

2 × 2 × 2 × ... N times
= 2ᴺ

Every subset is added to the result by creating a copy.

Copying one subset can take up to O(N) time.

Therefore,

Time Complexity = O(2ᴺ × N)

The first factor comes from generating every possible subset.

The second factor comes from copying each subset into the result.

Space Complexity

Let’s separate the auxiliary space from the output space.

Auxiliary Space

The recursion stack grows one level for every element.

Our shared subset list can also contain at most N elements.

So the auxiliary space is:

O(N)

A common question is:

“But aren’t we making two recursive calls?”

Yes.

However, the two recursive calls execute one after another.

They are not simultaneously present on the recursion stack.

Space complexity measures the maximum number of active recursive calls at any instant, not the total number of recursive calls made during the entire execution.

Output Space

The returned result contains:

2ᴺ

subsets.

Each subset can contain up to N elements.

Therefore, the output itself occupies:

O(2ᴺ × N)

This is usually reported separately because it is part of the required output rather than extra working memory.

Subsets introduces perhaps the biggest conceptual shift in backtracking.

Until now, recursion followed a structure that already existed.

Now recursion creates the structure through its decisions.

Once that idea clicks, the next problem feels like a natural extension.

Instead of deciding whether to include an element, we’ll decide which unused element should occupy the next position.

Permutations — When the Choice Is Which Element Comes Next

At first glance, Permutations looks very similar to Subsets.

We’re still given an array.

We’re still expected to generate every possible answer.

We’re still going to use recursion.

But there is one fundamental difference.

In Subsets, the question at every recursive call was:

Should I include this element?

Each element had exactly two choices.

In Permutations, that question no longer makes sense.

An element cannot simply be “included.”

Every element must appear exactly once.

The real question becomes:

Which unused element should occupy the next position?

That single change completely changes the recursive state.

Problem Statement

Given an array nums of distinct integers, return all possible permutations.

You may return the answer in any order.

Let’s Solve It Without Thinking About Recursion

Suppose we’re given:

nums = [1,2,3]

Forget recursion for a moment.

Let’s build one permutation manually.

What can we place in the first position?

1
2
3

Suppose we choose:

[2]

Now what choices remain?

1
3

Suppose we choose:

[2,3]

Only one unused element remains.

[2,3,1]

One complete permutation has been formed.

Notice something interesting.

Unlike Subsets, we aren’t making a decision about a particular index.

Instead, we’re repeatedly asking:

Among all the unused elements, which one should I choose next?

The Recursive State

In Subsets, our recursive state was:

(index, subset)

The index told us which element we were currently making a decision about.

That doesn’t work here.

Suppose we’ve already built:

currentPermutation = [2]

What does index = 1 mean?

Nothing useful.

The next element could still be 1 or 3.

Instead, our recursive state becomes:

(currentPermutation, visited)

• currentPermutation stores the partial permutation built so far.
• visited tells us which elements have already been used.

When Is a Permutation Complete?

A permutation is complete when every position has been filled.

In other words,

if (currentPermutation.size == nums.size)

At that point, we have one valid permutation.

Just like the previous problems, we store a copy because the same list will continue changing during recursion.

result.add(currentPermutation.toList())

Deriving the Recursive Calls

Suppose we have reached the following state.

nums = [1,2,3]
currentPermutation = [2]
visited = [false, true, false]

We’ve already placed 2.

What should we do next?

We simply iterate through every element.

If an element has already been used,

Skip it.

Otherwise,

Choose it.
Explore recursively.
Undo the choice.

The algorithm almost writes itself.

Choose

visited[i] = true
currentPermutation.add(nums[i])

Explore

dfs(...)

Undo

currentPermutation.removeAt(currentPermutation.lastIndex)
visited[i] = false

Notice something beautiful.

In Path Sum II, we restored one piece of state.

path

In Subsets, we restored one piece of state.

subset

In Permutations, we restore two pieces of state.

currentPermutation
visited

This leads us to one of the most important principles of backtracking.

Every piece of mutable recursive state that is modified during the “choose” step must be restored during the “undo” step before exploring another choice.

Complete Solution

class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val currentPermutation = mutableListOf<Int>()
        val visited = BooleanArray(nums.size)
        fun dfs() {
            if (currentPermutation.size == nums.size) {
                result.add(currentPermutation.toList())
                return
            }
            for (i in nums.indices) {
                if (visited[i]) continue
                visited[i] = true
                currentPermutation.add(nums[i])
                dfs()
                currentPermutation.removeAt(currentPermutation.lastIndex)
                visited[i] = false
            }
        }
        dfs()
        return result
    }
}

Time Complextiy

Let’s derive it instead of memorizing it.

For the first position, we have:

N choices

For the second position:

N - 1 choices

For the third:

N - 2 choices

Eventually, the total number of permutations becomes:

N × (N - 1) × (N - 2) × ... = N!

Every permutation is copied before being added to the result.

Copying one permutation takes:

O(N)

Therefore,

Time Complexity = O(N! × N)

The first factor comes from generating every possible permutation.

The second factor comes from copying each permutation into the result.

Space Complexity

Auxiliary Space

The recursion stack grows to at most:

N

The currentPermutation list also stores at most:

N

The visited array stores one boolean for every element.

N

Adding these together still gives:

Auxiliary Space = O(N)

Output Space

The result stores:

N!

permutations.

Each permutation contains:

N

elements.

Therefore, the output itself occupies:

O(N! × N)

Although the problems look completely different, they all follow the same rhythm.

1. Identify the recursive state.
2. Make one choice.
3. Explore recursively.
4. Restore the recursive state.
5. Try the next choice.

That’s backtracking.

It’s not a separate algorithm from DFS.

It’s simply DFS over a decision tree where we reuse mutable state safely by restoring it before exploring another possibility.

Once you begin looking for this pattern instead of memorizing templates, many backtracking problems become much easier to derive from first principles.