What is the retrospective method
Backtracking (exploration and backtracking) is a kind of selection of the best search method, also known as the trial method, according to the selection of the best conditions to search forward in order to achieve the goal. But when the exploration to a certain step, found that the original choice is not optimal or can not reach the goal, it will be returned to a step to choose again, this can not go back to go back to the technology for the backtracking method, and to meet the conditions of the backtracking of a certain state of the point is called "back to the point".
The problem of arranging all elements without duplicates
Given a list with all its elements distinct, it is required to return the full permutation of the list's elements.
Let n = len(list), then this problem can be considered as an n-forked tree, dfs this tree, the backtracking point in this problem is when the depth (i.e., the length of the templist) is n, and the backtracking condition is that the current element has already appeared in the templist.
Backtracking versus recursion:
Backtracking is an idea, recursion is a form of it
class Solution(object):
The #rtlist is used to store all the returns of all alignments, and the templist is used to generate each alignment.
def backtrack(self,rtlist,templist,nums):
if(len(templist) == len(nums)):
(templist[:])
else:
for i in nums:
if(i in templist): # If there is already an i in the current arrangement, then continue, which is equivalent to branch bounding, i.e., not searching the subtree of the current node.
continue
(i)
(rtlist,templist,nums)
() # Replace the ending element with the next value in nums, traversing the next subtree
def permute(self,nums):
rtlist = []
templist = []
(rtlist,templist,nums)
return rtlist
Tree structure when nums=[1,2,3]:
The key thing is to identify good branch limits as well as backtracking points.
There is a question of whether it is possible to remove the newly added elements from the nums at each recursion. In fact, the time complexity of this will not be reduced too much because it still takes some time to operate on the list, and the time complexity of the original solution is not too bad because of the branching limit.
Full Arrangement with Repeated Elements
The difference between this problem and the above is mainly the difference in branch bounds, you can't use the occurrence of duplicate elements as a backtracking condition anymore, otherwise all of them are not satisfied.
Here we should use a counter to record the number of times each element appears in the nums, if the current element exceeds the number of times, then return, but here there is another problem is that the same arrangement may occur more than once, the solution here is that the same layer is not allowed to duplicate the elements, there are two solutions, one is to pass directly into the distinct array, and the other is to use a collection of record The current layer has been used in the elements.
The first method:
from collections import Counter
class Solution(object):
def backtrack(self, rtlist, tmplist, counter, nums, length):
if len(tmplist) == length:#Backtracking point
(tmplist[:])
else:
for i in nums:# Traverse horizontally
if counter[i] == 0:#Branch limits
continue
counter[i] -= 1
(i)
(rtlist, tmplist, counter, nums, length)# Vertical traversal
counter[i] += 1
()
def permuteUnique(self, nums):
rtlist, tmplist, counter = [], [], Counter(nums)
length = len(nums)
(rtlist, tmplist, counter, list(set(nums)), length)
return rtlist
second type
from collections import Counter
class Solution(object):
def backtrack(self, rtlist, tmplist, level, counter, nums):
if len(tmplist) == len(nums):
(tmplist[:])
else:
for i in nums:
if i in level or counter[i] == 0:
continue
counter[i] -= 1
(i)
(i)
(rtlist, tmplist, set(), counter, nums)
counter[i] += 1
()
def permuteUnique(self, nums):
if not nums:
return []
rtlist, tmplist, level, counter = [], [], set(), Counter(nums)
(rtlist, tmplist, level, counter, nums)
return rtlist
In the recursive can not be used "=" to modify the parent function of the variable, because "=" can only change the variable pointing to, to modify the parent function of the variable to be modified directly in memory, for example, into the container can be directly found in the variable memory address. Usually use ().
For example in the above program if we want to recover the counter at the backtracking point we can't use counter = Counter(nums) but we should modify counter[key] one by one.
summarize
The backtracking method is actually to consider the original problem as a tree, we traverse the tree to return at the impossible, not at traverse the subtree of this node and return when the requirements are met.
So in the backtracking method, the key thing is to find reasonable branch limits (important), and return conditions.
More pleaseconsultation
Traversal methods for multinomial trees:
def travel(root):
Iterate over root
for subtree_root in All nodes in the current layer:
travel(subtree_root)
Traversal can be accomplished by performing travel on all nodes of a layer in for, and because travel is performed on all subtrees of all nodes.
This python backtracking method template above is all that I have shared with you, I hope to give you a reference, and I hope you will support me more.