Let’s talk about Backtracking
Introduction
Backtracking is something you absolutely need to understand when working with recursive calls. Once you grasp the concept, you’ll be able to understand and apply a wide range of advanced algorithms that involve trees, graphs, and dynamic programming. At the very least, you’ll come away with a solid idea of when and how to use it.
Prerequisite
Why should you care about backtracking?
You can think of backtracking as a smarter version of brute force. Instead of blindly trying every possibility, it strategically explores all potential solutions to a problem. You’ll need to understand backtracking to follow along with the articles coming up next. Make sure you’re comfortable with everything covered in the recursion article before diving into this one.
Backtracking in Action
As usual, let’s start with a problem.
https://www.geeksforgeeks.org/problems/power-set4302/1
Given a string S, find all the possible subsequences of the String in lexicographically-sorted order.
The key terms in this problem are bolded. A subsequence must preserve the original order of characters. For example, "ac" is a valid subsequence of "abc", but "ca" is not — because the order doesn’t match the original string. There’s also the concept of a subarray, which must be contiguous. For instance, "ab" is both a subsequence and a subarray, but "ac" is only a subsequence — not a subarray — because "b" is missing in between. That’s just a side note for extra context.
Let’s look at the example input/output. If the input string S is "abc", the expected output is ["a", "ab", "abc", "ac", "b", "bc", "c"].
Input: str = "abc"
Output: a ab abc ac b bc c
Explanation: There are 7 subsequences that can be formed from "abc"This type of problem is called a powerset problem. Formally defined:
A power set is the set of all possible subsets of a given set, including the empty set and the set itself. For a set with 𝑛 elements, its power set will contain 2^n subsets.
For example, if we treat the string "ab" as the set {"a", "b"}, its power set has 2² = 4 elements, because the power set includes the empty set. Visually:
original set = {"a", "b"}
subset = {"", "a", "b", "ab"}So for "abc", there should technically be 2³ = 8 subsets. But since the problem excludes the empty string "", we get 2³ - 1 = 7. Let’s work through it including the empty set for clarity.
We’ll start with "ab" to keep things simple. Initially, we have an empty string "". From there, two choices arise: we can either include the first character "a" (appending it to "" to get "a"), or skip it and keep "" as is. We’ll use "_" to represent the empty string visually.
Let’s draw out the decision tree based on these two choices — either include "a" or don’t:
string = a b
^
"_"
/ \
"a" "_"We’ve processed "a". Now only "b" remains. From each of the two leaf nodes "a" and "_", we again branch: include "b" or skip it. Starting from the leftmost node "a":
string = a b
^
"_"
/ \
"a" "_"
/ \
"ab" "a"That covers the "a" branch. Now for "_":
string = a b
^
"_"
/ \
"a" "_"
/ \ / \
"ab" "a" "b" "_"All characters have been used, so we can’t go further. The possible subsequences are "ab", "a", "b", and "". Excluding the empty string leaves us with three.
Now let’s extend this to "abc" and fill out the full decision tree:
string = a b c
^
"_"
/ \
"a" "_"
/ \ / \
"ab" "a" "b" "_"
/ \ / \ / \ / \
"abc" "ab" "ac" "a" "bc" "b" "c" "_"Let’s quickly walk through from left to right.
- Leaf
"ab"+"c"="abc", skip ="ab" - Leaf
"a"+"c"="ac", skip ="a" - Leaf
"b"+"c"="bc", skip ="b" - Leaf
"_"+"c"="c", skip ="_"
Since there are no more characters left in the original string, this is our base case. If you’ve read the previous article, you’ll remember the four things to consider when writing recursive functions. Worth noting: a tree that represents all possible states like this is called a state-space tree.
func allPossibleStrings(of s: String) -> [String] {
// TODO: Implement
}That’s the function shell. We’ll add a helper function to handle the recursion:
func helper() {
}Looking at the recursive tree above, we need to know which character we’re currently processing. At minimum, we need the original string (as a character array) and the current index. We also need a parameter to track the current built-up string, since the root node starts as "_" (empty):
func helper(_ chars: [Character], _ current: String, _ index: Int) {
}What should we return? The problem asks for a string array, so our helper should also return [String]:
func helper(_ chars: [Character], _ current: String, _ index: Int) -> [String] {
}We already identified the base case: when there are no characters left to process. At that point, we return the current string wrapped in an array:
func helper(_ chars: [Character], _ current: String, _ index: Int) -> [String] {
if index == chars.count {
return [current]
}
}The tree showed two decisions at each step. The first is to include the current character:
helper(chars, current + String(chars[index]), index + 1)The second is to skip it (we always increment the index to eventually reach the base case):
helper(chars, current, index + 1)Combining both branches gives us all possible subsequences for that path. If this is unclear, refer back to the recursive/decision tree. The complete code looks like this:
func allPossibleStrings(of s: String) -> [String] {
return helper(Array(s), "", 0)
}
func helper(_ chars: [Character], _ current: String, _ index: Int) -> [String] {
if index == chars.count {
return [current]
}
let withChar = helper(chars, current + String(chars[index]), index + 1)
let withoutChar = helper(chars, current, index + 1)
return withChar + withoutChar
}Run this with "abc" and you’ll see the output matches the leaf nodes of the recursive tree exactly. Since we need to exclude the empty string "" from the final result, we can filter it out. To be safe, here’s a clean version:
func allPossibleStrings(of s: String) -> [String] {
helper(Array(s), "", 0)
.filter({ !$0.trimmingCharacters(in: .whitespaces).isEmpty })
}Now you might be wondering — you said this was backtracking, but this just looks like regular recursion. It is recursive, yes. But backtracking is happening inside it. Let’s look at exactly where. Go back to the "abc" tree:
"_"
/ \
"a" "_"
/ \ / \
"ab" "a" "b" "_"
/ \ / \ / \ / \
"abc" "ab" "ac" "a" "bc" "b" "c" "_"The program runs like this:
"_" -> "a" -> "ab" -> "abc"It hits the base case and returns ["abc"]. Then the last stack frame is popped, and we’re back at "ab". From there, we take the “skip” branch and get ["ab"].
"_"
/
"a"
/
"ab"
/ \
"abc" "ab"That act of popping from the call stack and returning to a previous branch point — that’s backtracking. Think of it like navigating a maze with paths A, B, and C: if path C is a dead end, you backtrack to B, look for more options, and if there are none, go all the way back to A and try the next path. Methodically stepping back until you find unexplored branches — that’s exactly what backtracking does.
Let’s make this even clearer with another problem:
Given a non-negative integer n, find all n-letter words composed of ‘က’ and ‘မ’, and return them in a list of strings in lexicographical order.
(This is a localized version for fun — the original problem uses ‘a’ and ‘b’. Same idea.)
For n = 2, the output is ["ကက", "ကမ", "မက", "မမ"] — four combinations. For n = 3, there are eight.
Function shell:
func generateLetterCombination(of n: Int) -> [String] {
}Recursion is the natural tool for combinatorial problems like this. We’ll explore when to use what approach in a future article. For now, let’s focus on understanding backtracking.
When n = 1:
n = 1
""
/ \
က မJust two outputs: "က" and "မ". When n = 2:
n = 2
""
/ \
က_ မ_
/ \ / \
ကက ကမ မက မမFour outputs. For n = 3, each branch splits twice more, giving 2³ = 8. Each branching adds one of two options, and we branch n times total.
Let’s trace through n = 3 step by step:
n = 3
""
/ \
က__ မ__First character placed. Moving to the second:
n = 3
""
/ \
က__ မ__
/ \ / \
ကက_ ကမ_ မက_ မမ_And the third:
n = 3
""
/ \
က__ မ__
/ \ / \
ကက_ ကမ_ မက_ မမ_
/ \ / \ / \ / \
ကကက ကကမ ကမက ကမမ မကက မကမ မမက မမမNow where does backtracking come in? Starting from the left:
"" -> က__ -> ကက_ -> ကကက"ကကက" is a valid word. We backtrack to ကက_, where "က" was already used, so we try "မ" next and get "ကကမ".
ကကက ✓
ကကမ ✓ (backtracked to ကက_, added မ)Both branches of ကက_ are done. We backtrack to က__, try the "မ" branch to get ကမ_, then:
ကမက ✓
ကမမ ✓ (backtracked to ကမ_, added မ)The left half (က__) is fully explored. We backtrack to "" and take the right branch မ__, continuing the same pattern.
That’s backtracking in action — diving as deep as possible down the leftmost path, hitting the base case, stepping back up one level, exploring remaining branches, stepping back up again, and repeating. Every possible case gets covered, like sifting everything through a sieve.
Here’s the code:
func generateLetterCombination(of n: Int) -> [String] {
return helper("", n)
}
private func helper(_ s: String, _ n: Int) -> [String] {
// When the string reaches length n, return it as a single-element array
if s.count == n {
return [s]
}
// Recursive case that adds 'က' and 'မ' to the string and combines results
let with_က = helper(s + "က", n)
let with_မ = helper(s + "မ", n)
return with_က + with_မ
}Since we’ve already covered what to think about when writing recursive functions, I won’t go over it again here. Challenge yourself: can you identify the four key considerations in this code? Where are they applied, and why? If you’re stuck, drop a comment and I’ll walk you through it.
If you’ve followed everything so far, here’s a problem to try on your own:
It’s the same category as the problems we covered above.
Summary
Recursion is hard. Backtracking is even more subtle, which makes it harder to see at first. My goal here isn’t to have you generate backtracking solutions from scratch just yet — it’s to get you comfortable enough to read and understand backtracking code when you encounter it. Just like learning to read before you write.
As mentioned in the recursion article, drawing out the recursive tree to visualize what’s happening is crucial. For backtracking problems especially, I always draw the simplest, most minimal recursive tree I can before writing a single line of code. That tree tells me where to start. Being able to sketch that tree on your own is one of the most important skills you can build.
Next up, we’ll take a short break from algorithms and move on to tree data structures, now that you have both recursion and backtracking under your belt.
Until next time!
Comments are powered by Giscus (GitHub Discussions). Loading them fetches resources from GitHub.