解答回溯算法-DFS算法的若干疑问
Prerequisites
Before reading this article, you should learn:
This article uses the simplest examples to answer readers' questions about backtracking algorithms and DFS algorithms.
What is the Difference Between Backtracking and DFS Algorithms?
Many readers ask, "Why do you only write about backtracking algorithms and not about DFS algorithms?"
Some readers are also confused. The Backtracking Algorithm Core Framework mentions that the backtracking algorithm template involves making choices before recursion and undoing those choices after recursion, like this:
void backtrack(...) {
if (到达叶子节点) {
return;
}
for (int i = 0; i < n; i++) { // Corrected the syntax error here: changed ',' to ';'
// make a choice
...
backtrack(...)
// undo the choice
...
}
}But why do you sometimes see code "making choices" before the for loop and "undoing choices" after the for loop:
void backtrack(...) {
if (到达叶子节点) {
return;
}
// make a choice
...
for (int i = 0, i < n; i++) {
backtrack(...)
}
// undo the choice
...
}What is the difference between these two implementations?
Q&A
Let me first answer the second question: Why do you see two implementations? What is the difference between them?
The first implementation is the standard backtracking algorithm framework. The second one, if we need to distinguish, should actually be classified as a DFS (Depth-First Search) algorithm framework.
You can rename the recursive function to make the difference clearer:
// backtracking algorithm framework template
void backtrack(...) {
if (到达叶子节点) {
return;
}
for (int i = 0; i < n; i++;) {
// make a choice
...
backtrack(...)
// undo the choice
...
}
}
// DFS algorithm framework template
void dfs(...) {
if (到达叶子节点) {
return;
}
// make a choice
...
for (int i = 0; i < n; i++) { // Corrected the syntax error here: changed ',' to ';'
dfs(...)
}
// undo the choice
...
}To answer the first question, what is the difference between backtracking algorithms and DFS algorithms?
According to the summary in Binary Tree Series Algorithms (Guideline), their essence is the same, both are brute-force enumeration algorithms under the "traversal" mindset. The only difference lies in their focus: backtracking algorithms focus on "branches," while DFS algorithms focus on "nodes."
I will use the simplest multi-tree traversal code to illustrate the difference between backtracking algorithms and DFS algorithms. Here is the code for traversing a multi-tree:
void traverse(Node root) {
if (root == null) {
return;
}
for (Node child : root.children) {
traverse(child);
}
}This multi-tree traversal function can be transformed into a backtracking algorithm framework or a DFS algorithm framework.
For example, if I want to turn it into a backtracking algorithm, it would look like this:
void backtrack(Node root) {
if (root == null) {
return;
}
for (Node child : root.children) {
// Make a choice
printf("I'm making a choice on the branch between %s and %s", root, child);
backtrack(child);
// Undo the choice
printf("I'm undoing the choice on the branch between %s and %s", root, child);
}
}If I want to turn it into a DFS algorithm, it would look like this:
void dfs(Node root) {
if (root == null) {
return;
}
// Make a choice
printf("I'm making a choice at node %s", root);
for (Node child : root.children) {
dfs(child);
}
// Undo the choice
printf("I'm undoing the choice at node %s", root);
}So, do these two have any fundamental differences? Actually, no. It's just a matter of flexibly applying them based on the problem's requirements.
For instance, if a problem asks you to print every node in a multi-tree, you would use the DFS algorithm framework:
void dfs(Node root) {
if (root == null) {
return;
}
print(root.val);
for (Node child : root.children) {
dfs(child);
}
}If you insist on putting this print code inside the for loop, the final printed result will miss the root node of the entire tree:
void backtrack(Node root) {
if (root == null) {
return;
}
for (Node child : root.children) {
// if written this way, the root node of the tree will be missed
print(child.val);
backtrack(child);
}
}Of course, you can write it this way if you insist. Before calling the backtrack function, you just need to handle the root node separately, though it's a bit troublesome.
For classic problems like permutations and combinations, the focus is obviously on the branches. Notice the diagrams I drew in the previous article Backtracking Algorithm to Master Nine Variants of Permutations and Combinations — they all have deep meanings:
Why are the numbers drawn on the branches instead of the nodes? Because when you're exhaustively listing permutations and combinations, you're making choices at the branch positions (adding elements to track), and the nodes reflect the results of your choices (the state of track):
Understand this in conjunction with the code:
LinkedList<Integer> track = new LinkedList<>();
// the core function of backtracking algorithm
void backtrack(int[] nums) {
// the standard framework of backtracking algorithm
for (int i = 0; i < nums.length; i++) {
// make a choice
track.addLast(nums[i]);
// enter the next level of the backtracking tree
backtrack(nums);
// undo the choice
track.removeLast();
}
}Got it? So, I generally consider DFS and backtracking as the same algorithm. We can choose flexibly based on the problem's requirements.
Can the backtrack/dfs/traverse function have a return value?
Conclusion First
Theoretically, it's up to you, but I strongly recommend keeping the backtrack/dfs/traverse function as a simple traversal function with a void type. Don't give it a return value.
I understand that adding a return value to such traversal functions is meant to terminate recursion early, but there are clearer ways to achieve this, which I will explain below.
According to the summary in Binary Tree Series Algorithms (Guideline), recursive algorithms mainly have two thinking patterns: one is the "traversal" pattern, and the other is the "problem decomposition" pattern.
The problem decomposition pattern is likely to have a return value because it needs to calculate the current problem's result based on the sub-problem's results. The names of such functions should be meaningful, like int maxDepth(TreeNode root), which clearly indicates what the return value represents.
For the traversal pattern, we usually create a function named backtrack/dfs/traverse that simply traverses a multi-way tree, making it straightforward. If you mix in a return value, it implies that your function has a special definition? Then, what is your approach—traversal or problem decomposition? Without proper understanding, it's easy to get confused, and you might not even know how to use the return value as you write the code.
Let me make up a simple problem as a specific example: Given the root node of a binary tree and a targetVal, find any node in the tree with the value targetVal. If it doesn't exist, return null.
The function signature is as follows:
TreeNode findTarget(TreeNode root, int targetVal);This problem is quite simple and can be solved using both "Traversal" and "Divide and Conquer" approaches.
If you use the "Divide and Conquer" approach, the solution code would look like this:
// Define: input node root and target value targetVal, return the node with the value of targetVal in the tree rooted at root
TreeNode findTarget(TreeNode root, int targetVal) {
// base case
if (root == null) {
return null;
}
if (root.val == targetVal) {
return root;
}
// Use the definition to search in the left subtree
TreeNode leftResult = findTarget(root.left, targetVal);
if (leftResult != null) {
return leftResult;
}
// If not found in the left subtree, use the definition again to search in the right subtree
TreeNode rightResult = findTarget(root.right, targetVal);
if (rightResult != null) {
return rightResult;
}
return null;
}如果用「遍历」的思维，那么可能有读者就会写出这样的代码：
// record the answer
TreeNode res = null;
TreeNode findTarget(TreeNode root, int targetVal) {
traverse(root, targetVal);
return res;
}
// it's not recommended to write like this
boolean traverse(TreeNode root, int targetVal) {
if (root == null) {
return false;
}
if (root.val == targetVal) {
res = root;
return true;
}
return traverse(root.left, targetVal) || traverse(root.right, targetVal);
}Actually, this code is correct, but it can be a bit difficult to understand.
I would wonder why your traverse function has a return value? Since it has a return value, is this a way to break down the problem? It doesn't seem like it, as I don't see you using this return value to derive the result of the original problem.
Upon closer inspection, it becomes clear that this boolean return value is used to terminate the recursion once a valid answer is found, reducing redundant calculations.
So, what is my recommended approach? It's to let each function do its specific job. The traverse function should only be responsible for traversal, without a return value. Whether an answer is found can be controlled by an external variable.
For example, you can add an external found variable, or simply use whether the res variable is null to determine if an answer has been found:
// record the answer
TreeNode res = null;
TreeNode findTarget(TreeNode root, int targetVal) {
traverse(root, targetVal);
return res;
}
// standard binary tree traversal framework
void traverse(TreeNode root, int targetVal) {
if (root == null) {
return;
}
if (res != null) {
// an answer has been found, return directly, terminate recursion
return;
}
if (root.val == targetVal) {
res = root;
return;
}
// standard traversal framework, traverse all nodes of the binary tree
traverse(root.left, targetVal);
traverse(root.right, targetVal);
}Alright, with this explanation, it's clear to me that your traverse function is only used to traverse a binary tree, and I will study the specific logic in the pre-order, in-order, and post-order positions.
This is a simple example, but the principle applies to all recursive functions that use the "traversal" mindset. Especially when a problem only requires you to find a valid solution, it's recommended to keep the traversal function as a void type and use external variables to control the termination of recursion.
Where Should the Base Case and Pruning Be Written?
What does this question mean? For example, in the simplest binary tree traversal framework, I usually write it like this:
void traverse(TreeNode root) {
// base case
if (root == null) {
return;
}
// pre-order position
traverse(root.left);
// in-order position
traverse(root.right);
// post-order position
}那有些读者可能会这样写：
void traverse(TreeNode root) {
if (root!= null && root.left != null) {
traverse(root.left);
}
if (root!= null && root.right != null) {
traverse(root.right);
}
}Both of these writing styles are fine, but my usual habit is to move all the judgment logic that can be mentioned at the beginning of the function to the beginning. This is because the recursive part is where you fill in the pre-order, in-order, and post-order code, and it's best not to mix it with the base case logic to avoid confusion. For example, in the above style, where are your pre-order, in-order, and post-order positions? Isn't it a bit unclear?
However, when I optimize backtracking algorithms, I tend to place the pruning logic before the recursion, like this:
void backtrack(...) {
// base case
if (到达叶子节点) {
return;
}
for (int i = 0, i < n; i++) {
// pruning logic
if (第 i 个选择不满足条件) {
continue;
}
// make a choice
...
backtrack(...)
// undo the choice
...
}
}I think this approach is clearer because you're pruning away invalid choices, so placing it before making a decision seems very reasonable.
However, in most cases, moving this pruning logic to the beginning of the function, alongside the base case, also works. It really depends on personal preference. As long as the answer is correct, you can write it however you like.