Closed alehro closed 1 week ago
exalate-issue-sync[bot]
commented
1 month ago Epiphania_Ekenimoh commented: Hello,
Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.
If you have any further questions or concerns in the meantime, please feel free to let us know.
Best regards, LeetCode Support Team
exalate-issue-sync[bot]
commented
1 week ago Epiphania_Ekenimoh commented: Thank you for your time.
Your feedback has been used to enhance the problem. As a token of our appreciation, your LeetCode account has been credited with 100 LeetCoins.
If you have any more questions or additional feedback, please don't hesitate to let us know. Your continued support is invaluable to us!
Best regards, The LeetCode Team
LeetCode Username
Alehro
Problem Number, Title, and Link
https://leetcode.com/explore/interview/card/leetcodes-interview-crash-course-data-structures-and-algorithms/711/backtracking/4535/
Bug Category
Problem description, Editorial
Bug Description
"Backtracking is an optimization that involves abandoning a "path" once it is determined that the path cannot lead to a solution."
This is definition of pruning, not backtracking.
I discovered that something is wrong with the definition when tried to understand where is "abandoning" in the given examples. See next page of the course - Generations, Example 1: 46. Permutations . There is no abandoning/pruning in the provided solution. It just runs trough all possible paths.
To clarify the situation I went to Skiena S, "The Algorithm Design Manual". He defines:
"Backtracking is a systematic way to run through all the possible configurations of a search space."
There is nothing said about pruning. Because they are two independant techniques. Yes, they are often used together. But it doesn't mean that they are logically connected.
This text again contradicts to the Example 1. This example does exhaustive search. Exhaustive search is not mutually exclusive with backtracking.
"In an exhaustive search, we generate all possibilities and then check them for solutions. In backtracking, we prune paths that cannot lead to a solution, generating far fewer possibilities."
Backtracking can be exhaustive. It may contain prune but may not.
Moreover, I believe the pruning can be done not only in backtacking. Literally any algorithm multiple paths can prune/abandon some paths.
What is disappointing is that in wiki the definion is almost the same. Hence, very confusing.
Language Used for Code
None
Code used for Submit/Run operation
No response
Expected behavior
Unfortunately Skiena's definition is not complete. It should be something like:
"Backtracking is a systematic way to run through all the possible configurations of a search space." What distinugushes the approach is the backtrack step.
Screenshots
No response
Additional context
No response