回溯法与枚举法

大家好，欢迎来到IT知识分享网。

1 回溯法应用

回溯法，顾名思义，生活中有一类人，很执拗，比如我，不到黄河心不死，到了黄河怎么办？往回走呗，难不成跳下去？

回溯法解决的问题有全排列，全组合，枚举什么的。

比如，给定一串不重复字母，让你按字典顺序进行排列，这是个全排列的问题，很好理解，但编程很麻烦。如果给定的字母可以重复，让你按字典的顺序排列，这个问题是不是更复杂了呢？

回溯法，跟数一样，随机取出一个元素，此时情况有N种，则有N个这有的节点，然后在剩下的集合中，又随机取个数，此时情况可能有N-1种（可能小于N-1如果有重复的项），重复上面的生成节点的过程。当处理到最后一个元素或者当前的路径以及不满足要求了，就往回走了，递归回来。

回溯构建数的时候，取出了那个元素，下一个集合就没有这个元素了。

2 回溯法固化模板

回溯法就相当于搜索一棵树，使用深度优先搜索数的方法。

def dfs(输入):
    if 当前状态为边界：
        记录或输出
        return 

    for i in range(len(输入))：#横向遍历所有子节点
        目前遍历的当前子节点
        if 子状态满足约束条件：
            dfs(子状态)
        

3 题集

3.1 字符串排列（全排列问题）

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

解题思路：字典排序，重复元素的全排列。深度优先搜索，即为空是返回．先从Ｎ个样本中取一个，接在递归在剩下的样本中取，为什么要递归？因为这样再取完以后会退回到上一级．

重复原始处理，排好序后，如果取到的这个，和上个相似，就continue．

假设根就是空，第一层会有N个子节点，对重复的取一个X，然后从集合中去掉取出的这一个X（重复的也去掉一个），迭代。

class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        ss = sorted(ss)
        temp = []
        N = len(ss)
        def dfs(ss,cur):
            if not ss:
                if len(cur) == N:
                    temp.append(cur)
                return
        for i in range(len(ss)):
            if i > 0:
                if ss[i] == ss[i-1]:
                    continue
            if len(ss) == N:
                cur = ss[i]
            else:
                cur = cur+ss[i]
            if i+1 < len(ss) and i>0:
                ss1 = ss[:i]+ss[i+1:]
            elif i==0:
                ss1 = ss[i+1:]
            else:
                ss1 = ss[:i]
            dfs(ss1, cur)
        dfs(ss,'')
        return temp

3.2 矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路：首先输入的是字符串‘ csadee’，需要映射成矩阵（嗯，绕了很长时间）。因为起始位置是随机的，所以需要遍历所有的矩阵作为起始位置。为了节约时间，我们需要剪枝，即如果当前位置的值不等于path，那就可以直接返回。

还需要注意一个约束，就是不能往回走，最开始我的代码是：

class Solution:
    def __init__(self):
        self.flag = False
    def hasPath(self, matrix, rows, cols, path):
        if not matrix:            
            return False
        for j in range(rows):
            for i in range(cols):
                self.hasp(matrix,j,i,path[:], rows)
                if self.flag:
                    return True
        return False

    def hasp(self,matrix, curr, curc, path, rows, cols):
        if not path:
            self.flag = True
            return
        if curr<0 or curc<0 or curr>rows-1 or curc>cols-1:
            return
        index = curr * cols + curc
        if matrix[index] == path[0]:
              
            self.hasp(matrix, curr-1, curc, path[1:], rows, cols)
            
            self.hasp(matrix, curr + 1, curc, path[1:], rows, cols)
            
            self.hasp(matrix, curr , curc - 1, path[1:], rows, cols)
            
            self.hasp(matrix, curr , curc + 1, path[1:], rows, cols)

本地跑属于False的也会返回True，什么原因呢？因为我重复了曾经的路径，贴上正确的代码：

class Solution:
    def __init__(self):
        self.flag = False
    def hasPath(self, matrix, rows, cols, path):
        if not matrix:            
            return False
        for j in range(rows):
            for i in range(cols):
                self.hasp(matrix,j,i,path[:], rows, cols,[(j,i)])
                if self.flag:
                    return True
        return False

    def hasp(self,matrix, curr, curc, path, rows, cols,history):
        if not path:
            self.flag = True
            return
        if curr<0 or curc<0 or curr>rows-1 or curc>cols-1:
            return
        index = curr * cols + curc
        if matrix[index] == path[0]:
            if (curr-1, curc) not in history:            
                self.hasp(matrix, curr-1, curc, path[1:], rows, cols,history+[(curr-1, curc)])
            if (curr + 1, curc) not in history: 
                self.hasp(matrix, curr + 1, curc, path[1:], rows, cols,history+[(curr + 1, curc)])
            if (curr , curc-1) not in history: 
                self.hasp(matrix, curr , curc - 1, path[1:], rows, cols,history+[(curr, curc-1)])
            if (curr , curc+1) not in history: 
                self.hasp(matrix, curr , curc + 1, path[1:], rows, cols,history+[(curr , curc+1)])

3.2 矩阵中的路径

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解题思路：数位之和，我想到的就是把它转换成str，然后按位读取str，转换成int并求和。感觉这道题很简单啊，思路也对，时间复杂度总是超了。我原来的思路跟上道题一样，边界条件改了（超出矩阵和数位之和），其实条件就只为（0,0）。调了很久，后来知道是走过的路径应该设置为全局变量。当初没有设置为全局变量。

正确代码：

class Solution:
    def movingCount(self, threshold, rows, cols):
        self.row, self.col = rows, cols
        self.dict = []
        
        self.search(threshold, 0, 0)
        return len(self.dict)

    def search(self, threshold, i, j):
        ss = 0
        for k in str(i)+str(j):
            ss = ss+int(k)
        if ss > threshold:
            return
        self.dict.append((i,j))
        if i != self.row - 1 and (i+1,j) not in self.dict:
            self.search(threshold, i + 1, j)
        if j != self.col - 1 and (i,j+1) not in self.dict:
            self.search(threshold, i, j + 1)