什么是回溯算法，以及什么时候会用到
回溯算法和递归有关系。它是利用递归来寻找一个问题的所有解，例如一个数组的排列组合所有的可能，还有Leetcode 980题目所说的求出所有可能的路径。
回溯与递归的区别：
递归是函数不断地自己调用自己，直至达到某个零界点后进行层层地返回，最后输出结果。
回溯是利用递归实现的一种算法，在递归的基础上，加上了剪枝的操作，就好比说达到某个条件，就提前返回，不会彻底走完整个递归的过程。还有另外一点就是使用回溯时要记住重置状态，以免影响回溯时下一个分支的结果。
总结一下：
我们可以把递归看作一个 算法结构，而回溯看作一个利用 算法结构 实现的一个 算法思想
接下来我们看两个实例 Leetcode 46和Leetcode 980，一个中等难度和高等难度的题目。
Leetcode 46 全排列：
Leetcode 46 全排列
谈一下解题思路：
输出的结果是全排列，换句话说就是求出所有的解，还记得我们刚刚说过的嘛？要求出一个问题的所有解，就需要用到回溯法，需要借助计算机帮助我们穷举出所有的可能。
现在我们知道了要用回溯来求解，回溯需要用到递归，那么如何来解答这个全排列的问题呢？
我们需要手推一下这个过程再来实现，所有的算法题都是这样哦！
Leetcode官方给的例子我们可以看到，由于有三个元素：1，2，3，答案也被分成了3个部分：1XX，2XX，3XX。
也就是原数组的第一个元素1的位置分别于元素2和3的位置做了一个调换。因此我们可以一直循环这个过程：
1元素和1元素进行调换，2元素和2元素进行调换，3元素和3元素进行调换，结果是数组123本身。
接下来，2元素和3元素进行调换，结果是132。
然后恢复123数组，将1元素和2元素进行调换,接下来最后的两个数字又开始自身和自身调换，然后再交叉互换，分别得到结果213和231。
然后恢复123数组...........
尤其要注意在交换后要恢复123数组本身，不然会产生重复但是又不全的排列组合哦。这一点要自己慢慢体会。因为要让每一个元素都有到第一位的机会，如果不恢复的话就错乱了。
接下来我们可以尝试编程：
对于刚接触的人，可能还是比较不好理解，希望多做题就能感受到吧。我也是这么来的，就是因为不是很理解，所以才通过这种方式让自己记忆更深刻。因为递归中间的过程，是很抽象的。
class Solution(object):
def permute(self, nums):
length = len(nums) #数组长度
res = [] #存放结果的数组
def swap(nums,p,i):
nums[p],nums[i] = nums[i],nums[p]
def perm(nums, p, q): #p q是用来记录递归子序列的首尾
#当p==q时，遍历到最底层了子问题只有一个元素了不能进行交换了，就把结果append到res数组中，这里要注意做一个深拷贝，不然会随着后面计算的变化而变化，答案会全部变成一样的结果。
if p==q:
temp = [0 for _ in range(0,q)]
for k in range(0,q):
temp[k] = nums[k]
res.append(temp)
for i in range(0,q):
swap(nums,p,i) #交换p和i下标对应的数字
perm(nums,p+1,q) #对子问题进行全排列
swap(nums,p,i) #当前组子排列结束后要恢复原来的数组模样
perm(nums, 0, len(nums))
return res
Leetcode 980 不同路径III：
Leetcode 980 不同路径III
谈一下解题思路：
这一题与上一题不同，就直接自上而下按逻辑编程就好。我们直接来看一下代码把，具体我会放上注解。
需要注意的还是一些问题处理的小细节，例如如设置走过的路为障碍，递归回上层之前要进行一个障碍的恢复。
具体的结构就是 移动+判断移动是否合法
class Solution(object):
def uniquePathsIII(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
SPACE = 0
START = 1
EXIT = 2
OBSTACLE = -1
SPACE_COUNT = 0
global PATH_COUNT #要被后面函数用到 记录合法路径数目
PATH_COUNT = 0
R, C = len(grid),len(grid[0])
sr,sc = 0, 0
udlr = ((-1,0)(1,0)(0,-1)(0,1)) #定义上下左右走
for r in range(0,R):
for c in range(0,C):
#记录有多少个可行走的位置，因为题目要求要走完所有的SPACE
if grid[r][c] == SPACE:
SPACE_COUNT+=1
#记录起始点
elif grid[r][c] == START:
sr, sc = r, c
#判断下一步是否合法
def is_valid_pos(r,c):
if r < 0 or c < 0:
return False
if r < R, c < C:
return grid[r][c] == SPACE or grid[r][c] == EXIT
return False
def visit(r,c,visited_count):
global PATH_COUNT
#判断递归返回条件
if grid[r][c] == EXIT:
if SPACE_COUNT == visited_count:
PATH_COUNT+=1
return #如果走到了EXIT但是没有走满所有的SPACE，就会被返回，路径不加1
temp = grid[r][c]
grid[r][c] = OBSTACLE
for dr,dc in udlr:
nextr,nextc = r+dr,c+dc
if is_valid_pos(nextr,nextc):
visit(nextr,nextc,visited_count+1)
grid[r][c] = temp
visit(sr,sc,0)
return PATH_COUNT
网友评论