Anyone knows a LeetCode problem showing Backtracking that abandons a candidate ("backtracks") as soon as it determines that the candidate cannot lead to a valid solution.
Below is quoted from the link below:
"Backtracking is a general algorithm for finding all (or some) solutions to some computational problems (notably Constraint satisfaction problems or CSPs), which incrementally builds candidates to the solution and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot lead to a valid solution. [1] "
https://leetcode.com/explore/learn/card/recursion-ii/472/backtracking/2654/
Like the example 1 in the link above, but what does the code for the example look like in relation to Backtracking?
For example of the N-Queen II question, it seems the Backtracking is the " if is_valid(next_candidate)" below, not the "remove(next_candidate)" statement as mentioned on template below from https://leetcode.com/explore/learn/card/recursion-ii/472/backtracking/2793/
def backtrack(candidate):
if find_solution(candidate):
output(candidate)
return
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)
What are your thoughts?