20200804更新-回溯总结

回溯用于解决【1-n个元素的排列或组合问题】

• 1.未优化的回溯算法需要遍历完所有的情况，一共是n(n-1)(n-2)...1即n!种，时间复杂度O(n!)，是所有复杂度里面最大的。。。

• 2.将原集合的子集看做子问题，做了子集备忘的回溯每个子问题只需要计算一次，而子问题的个数是2^n， 时间复杂度O(2^n)，是所有复杂度里面正数第二大的。。。但是！这个复杂度也比O(n!)强多了。那么什么情况下可以使用【划分成 2^n个子集】呢？【解具有局部无序的特征】当只要求组间有序而组内无序的时候，如假设序列ABCDE为所求，但实际上BACED\ABDCE也都满足题意，AB一组，CDE一组，组间有序，组内无序——换句话说，无论先A后B，还是先B后A，都能够让问题演进到同样的状态。这一题的经典例题就是#### 312. 戳气球 and #### LCP 13. 寻宝 寻宝这题更难发现局部可无序这一潜在解特征。简单来讲就是，有M个机关要破解，机关之间的距离不同，找最短路径。一拿到估计就想回溯，时间复杂度M!，要优化一下。把M个机关映射到bitmap上面去，这样子问题数量缩减成2^M， 而不同子问题间存在递推关系，有递推就可以DP了

• 3.【进阶】将原集合的子区间看做子问题，如集合[1,2,3,4,...,n]，def(0, n)作为当前区间问题的解，则def(0, n) = best( def(0, i) + def(i, n), 0<=i<=n )。做了子区间备忘的回溯每个子问题只需要计算一次，而子问题的个数是n方，时间复杂度O(n^2)。这时实际上变成了更一般化的递归问题，无需状态复原。见 leetcode312. 戳气球，leetcode140. 单词拆分 II
  这里对140单词拆分进行简单分析

140. 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
     说明：
     分隔时可以重复使用字典中的单词。
     你可以假设字典中没有重复的单词。

例如输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

分析：
首先第一个想法肯定是暴力回溯，维护一个全局变量ans，当回溯到底的时候做结果结算，时间复杂度O(n!)，n为s的长度
优化一下，考虑到某个子字符串s’可能会被重复计算，也就是会出现重复子问题，我们通过hashtable把子问题的解记录下来。具体地，对每一个字符串s，记录它的字典解析结果，不可解析时记录为[]，通过记录实现剪枝，让整个问题从回溯转为记忆化dfs

class Solution:
    def __init__(self):
        self.res_dict = dict()

    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        return self.dfs(s, wordDict)

    # 记忆化dfs
    # dfs返回值: s对应的题目所求List[str]
    def dfs(self, s, wordDict):
        res = []
        # 递归出口。如果s为''，说明原始整个字符串已经顺利解析，返回非空的['']表示解析完毕；而返回[]则表示s不可解析
        if not s:
            return ['']
        
        if s not in self.res_dict:
            for i in range(len(s)+1):
                temp_word = s[:i]
                if temp_word in wordDict:
                    # dfs
                    behind_res = self.dfs(s[i:], wordDict)
                    # 如果behind_res为[]，说明s[i:]不能进行字典解析，整个s也就不能顺利解析
                    for sentence in behind_res:
                        res.append(temp_word+(' '+sentence if sentence else ''))                                       
            self.res_dict[s] = res
        return self.res_dict[s]

小结：
当问题等价于求一个排列或者组合时，往往可以考虑回溯，很大概率命中
关键点就在于识别出这是个排列组合问题
一般地，求顺序的问题就是求排列，求子集的问题就是求组合

1、理解回溯

回溯就是回退，就是撤步/step back
举个例子，寻宝：

回溯简明图解

2、回溯要点

• 回溯问题是树形结构问题

**事实上，回溯问题是一个树形结构的问题，因为不断前进与回溯的过程会生长出一棵树--我叫做前进回溯树(forward back tree, FBT)

• 回溯 = 深度优先遍历 + 状态复原 + [剪枝] (根据具体问题判断是否剪枝)

还是借用寻宝来理解

回溯树形图解

如图，假设只有C点有宝藏，寻宝的路程如图所示，其中黄色箭头表示叶结点向上回溯

• 首先，人从起点到A到D，发现没有宝藏，回退到A；
• 然后从A来到E处，发现没有宝藏，又回退到A；
• 然后从A来到F处，发现没有宝藏，又回退到A；
• 这时发现从A无论如何都到不了宝藏点，于是回退到起点
• ......如此反复
• 直到最终找到宝藏点C

由此我们可以看到，

• 对于寻宝问题形成的FBT树，寻宝的过程遵循深度优先遍历，即先尝试一条路走到黑，达不到目的再step back；
• 而step back，必须保证问题的各个状态回到上一结点的状态，即状态复原，如从D点回到A点，问题的状态需要恢复到A点的状态

  状态复原是回溯最最重要的一点

• 可剪枝。对于某些回溯问题，可以通过避免不必要的前进（如只需找到一个解，那么找到之后就无需继续搜索）、按结点值的大小顺序构造树等操作来进行剪枝，减少多余计算

3、回溯问题模板

将问题对应一颗FBT树，解决问题的过程就是不断生长这棵树的过程。如何生长这棵树呢？

backtracking

backtracking(all_current_state)，all_current_state包括当前已选路径visited_path+当前可选择列表choice_list+回溯出口target

• 1.首先利用参数判断当前状态下是否进行结果结算
• 2.从选择列表中选择一个son结点，将问题状态 更新为 son结点处对应的问题状态，表示选择son结点后问题来到了son结点处。【更新必须包括全部三项：visited_path+choice_list+target】
• 3.递归调用自己
• 4.递归返回后，进行状态复原，将前面第二步中修改的状态改回去

def backTrack(visited_path, choice_list, result, target):
        # visited_path, choice_list, target 这3种参数是必须的
        # visited_path表示当前的问题阶段，choice_list表示当前问题面临的可选项，target出现表示问题无需继续向下搜索，这时result用于结算可行解，
        # 递归出口
        if visited_path meets target:
            update result
            return
 
        # 尝试结点每一个可能的选择
        for c in choice_list:
            # 2.更新问题状态: 必须包含3项，visited_path+choice_list+target
            visited_path.add(c)
            new_choice_list = choice_list.remove(c)
            update target
            # 3.递归
            backTrack(visited_path, new_choice_list, result, target)
            # 4.状态复原
            visited_path.remove(c)
            reset target

4、回溯解决的问题

很简单，就2类，排列类问题和组合类问题。

• 排列类问题。每条路径对应一个排列，特点是路径可以纵向自由生长，不遵循某种约束规律
• 组合类问题。在数学上，组合就是在排列的基础上消序；对应到回溯树上，就是在回溯树每次纵向向下生长的时候，必须遵循一定的规律，使得到整个路径是按照特定规律生成的，从而实现消序

因此，更抽象地来看，回溯解决的问题是【求解自由路径问题】和【求解有序路径问题】

5、例子

给定一个没有重复数字的序列，返回所有全排列
分析：
这是一个排列类问题，遍历完整个回溯树，叶子节点结算路径即可

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        l = len(nums)
        used = [False] * l
        result = []
        cur_result = []
        self.backTracking(cur_result, used, nums, result)
        return result
        
        
    def backTracking(self, cur_result: List, used: List, nums: List, result: List):
        '''
        visited_path 用 cur_result表示，存放起点至当前结点形成的排列
        choice_list 可用 used: List & nums: List求出
        target  用cur_result长度 == nums长度表示
        
        used: List 标记序列中的某个元素是否被使用，长度与nums一致。
        result: List 用于存放给定序列的所有全排列                
        '''
        
        # 回溯出口
        if len(cur_result) == len(nums):
            # 结果结算
            print('result update')
            result.append(cur_result.copy())
            return
        
        for i in range(len(used)):
            # 如果元素未被使用，这些元素组成模板代码中的choice_list
            if not used[i]:
                # 更新状态：更新cur_result和used[i]，target不变不用修改
                cur_result.append(nums[i])
                print('cur_result is %s' % str(cur_result))
                used[i] = True
                # 对结点进行操作，这里是进行递归操作
                self.backTracking(cur_result, used, nums, result)
                # 递归结束，恢复原来的状态
                used[i] = False
                cur_result.pop()

输入nums = [1,2,3]，打印过程如下，显示了整棵FBT的生长过程

cur_result is [1]
cur_result is [1, 2]
cur_result is [1, 2, 3]
result update
cur_result is [1, 3]
cur_result is [1, 3, 2]
result update
cur_result is [2]
cur_result is [2, 1]
cur_result is [2, 1, 3]
result update
cur_result is [2, 3]
cur_result is [2, 3, 1]
result update
cur_result is [3]
cur_result is [3, 1]
cur_result is [3, 1, 2]
result update
cur_result is [3, 2]
cur_result is [3, 2, 1]
result update

返回：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

有了本题的基础，我们可以给出求排列组合的一般形式：
以升序形式给定n个数，并指定一个k(0<k<=n)，求这n个数中所有可能的k个数的排列以及组合

显然，求n个数中所有k个数的排列，只是在上题的基础上，限制了树的深度。当len(visited_path)==k时，停止生长，即为target
而求n个数中k个数的所有组合，只需要在求排列的基础上进行消序操作即可。例如[1,2,3]和[2,1,3]是2个排列，但属于同一个组合。因此只需要选取排列中特定的一个作为组合结果，选升序的排列或者降序的排列都行。这也就是说，路径必须是升序或者降序的

class Solution:
    def combine(self, nums: list, k: int) -> List[List[int]]:
        n = len(nums)
        used = [False] * n
        layer_count = 0
        cur_result = []
        result = []
        self.backTracking(nums, used, cur_result, result, k)
        return result

    def backTracking(self, nums, used, cur_result, result, k):
        if len(cur_result) == k:
            result.append(cur_result[:])
            return
        else:
            for i in range(len(nums)):
                if not used[i]:
                    # 如果求组合，加入这句判断，通过形成升序的路径进行消序
                    if cur_result and nums[i] < cur_result[-1]:
                        continue
                    # 修改状态，visited_path + choice_list，target一直不变
                    used[i] = True
                    cur_result.append(nums[i])
                    # 递归
                    self.backTracking(nums, used, cur_result, result, k)
                    # 状态恢复
                    used[i] = False
                    cur_result.pop(-1)

趁热打铁
leetcode 40.
给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合，并且candidates中的每个数字在每个组合中只能使用一次

说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例1:
输入: candidates =[10,1,2,7,6,1,5], target =8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
原链接
分析：
看题，直接告诉我们，求的是【组合】。那么就需要设定路径的纵向生长顺序或者说生长规律。因此，这个规律可以是，将一个数num纳入路径后，再纵向生长的路径只能由num后面的数组成（这是万能的求组合的路径纵向生长规律）。这里有个小tip，我们选择将candidates先做个升序排序，这样一旦我们找到一个符合条件的路径，就可以进行剪枝。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        part_result = []
        used = [False] * len(candidates)
        # 先排序candidates
        candidates = sorted(candidates)
        # 回溯
        self.backTracking(part_result, candidates, target, result)
        return result
        
            
    # 回溯函数    
    def backTracking(self, part_result, choice_list, target, result):
        # part_result 表示 visited_path
        # choice_list 表示 choice_list
        # target

        ## 到达叶子节点，返回True来实现剪枝。因为target < 0或者target == 0说明不用再纵向往下生长了，同一层也不需要横向生长了
        if target < 0:
            return True
        if target == 0:
            result.append(part_result.copy())
            return True

        last_ele = None
        for i in range(len(choice_list)):
            ele = choice_list[i]
            # 如果ele与同一层的前一个ele值相同，那么会纵向生长出相同的树枝就不满足题意。因此需要横向判断ele与同一层的前一个ele值
            if last_ele != ele:
                last_ele = ele

                # 修改3个状态。visited_path+choice_list+target
                part_result.append(ele)
                temp_target = target - ele
                # 递归。每次的choice_list都是candidates中ele之后的元素
                break_flag = self.backTracking(part_result, choice_list[i+1:], temp_target, result)
                # 状态复原
                target = temp_target + part_result.pop()
                # 根据break_flag进行【横向剪枝】
                if break_flag:
                    break
            else:
                continue
        ## 不是回溯树的叶子节点，【返回false表示不横向剪枝】
        return False                

递归返回后必须马上进行状态复原！！！！！！！！！！！！

还有 leetcode 51. N 皇后
N皇后问题，也是需要不断地尝试，当皇后不能以合法的位置放置时，回溯进行新的尝试，直到找到合法的放置方法

对于一个n X n的棋盘，我们希望从上往下逐行合法地放置一个皇后
那么，

• 维护一个queen_pos作为阶段性结果集，保存当前已经放置好的皇后的位置
• 维护一个dict，dict[pos] > 0 表示当前情况下pos位置非法，该位置属于dict[pos]个皇后的势力范围，现在不可以放置新皇后；如果dict[pos] == 0，则可以在此放置皇后
  我们每放置一个皇后，就把行、列和两个斜线上的所有位置的字典值+1；每次回溯移除一个皇后，就把相应的字典值-1
  理清思路后，代码也可以清晰地写出

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 设置好规则，【dfs】暴力尝试所有解。如果能够dfs到第n层的，说明整个路径上的皇后位置合法，纳入结果集。
        # 用queen_pos list记录可行的皇后位置；用字典invalid_pos记录当前不可放置的位置，0可放，非0不可放
        queen_pos = list()
        invalid_pos = dict()
        for i in range(n):
            for j in range(n):
                invalid_pos[(i,j)] = 0
        final_res = []

        def helper(queen_pos, invalid_pos, row_index, final_res):
            # 已经到整个棋盘的n行，说明0-n-1行都放好了，结算并返回
            if row_index == n:
                temp = []
                for p in queen_pos:
                    s = '.'*p[1] + 'Q' + '.'*(n-1-p[1])
                    temp.append(s)
                final_res.append(temp)
                return

            for i in range(n):
                pos = (row_index, i)
                if invalid_pos[pos] == 0:
                    # 尝试放一个皇后
                    queen_pos.append(pos)
                    ## 更新不可放的位置 ##
                    additional_invalid_pos = []
                    for j in range(n):
                        # 同一行不可再放
                        additional_invalid_pos.append((row_index, j))
                    for j in range(n):
                        # 同一列不可再放
                        additional_invalid_pos.append((j, i))
                    s = row_index + i
                    delta = i - row_index
                    for j in range(n):
                        # 双斜线不可再放
                        if n > s-j >= 0 : additional_invalid_pos.append((j, s-j)) 
                        if 0 <= j + delta < n: additional_invalid_pos.append((j, j+delta)) 
                    for ele in additional_invalid_pos:
                        invalid_pos[ele] += 1
                    ## 更新不可放的位置，完毕 ##
                    # dfs
                    helper(queen_pos, invalid_pos, row_index+1, final_res)
                    # 状态复原
                    queen_pos.pop()
                    for ele in additional_invalid_pos:
                        invalid_pos[ele] -= 1
        
        helper(queen_pos, invalid_pos, 0, final_res)
        return final_res

6、再进阶一下

在上面的问题中，问题起点都是唯一的，即只有一个根结点，只产生一棵FBT树。但有时候，会存在多个问题起点，那么我们就需要对应产生多棵FBT树

例如leetcode79题：
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用

示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

分析：
以word = "ABCCED"为例

字符串以A开头，那么搜索的起点可以是board[0][0]，也可以是board[2][0]，起点有多个。对每一个起点，都要进行尝试

当访问完某个字符时，问题下一步可以去的位置是这个字符的上下左右位置，但注意，上下左右中溢出board边界的位置和已经访问过的位置要剔除，剔除后的位置就是可以去的一个个可选项

class Solution:
    def __init__(self):
        self.res = False

    def exist(self, board: List[List[str]], word: str) -> bool:
        n = len(board)
        m = len(board[0])
        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0]:
                    visited_path = [(i,j)]
                    all_neibor = self.getNeibor(board, (i,j))
                    self.backTracking(visited_path, board, all_neibor, word[1:])
                    if self.res:
                        return True
        return False

    
    def getNeibor(self, board, pos):
        n = len(board)
        m = len(board[0])
        a, b = pos[0], pos[1]
        for i, j in [a, b-1],[a,b+1],[a-1,b],[a+1,b]:
            if 0 <= i < n and 0 <= j < m:
                yield (i, j)

    # 核心代码
    def backTracking(self, visited_path, board, all_neibor, target):
        # visited_path, list类型，记录走过的路径
        # visited_path和all_neibor结合可求出choice_list
        # target, 待查找的字符串

        if target == '':
            self.res = True
            return 
        
        for pos in all_neibor:
            if board[pos[0]][pos[1]] == target[0] and pos not in visited_path:
                # 改变visited_path的状态
                visited_path.append(pos)
                new_all_neibor = self.getNeibor(board, pos)
                self.backTracking(visited_path, board, new_all_neibor, target[1:])
                # 改回visited_path的状态
                visited_path.pop()
                if self.res:
                    return

7.进一步思考，回溯与dp的不同之处

回溯和dp看似有点相似，一个自顶向下，一个自底向上，但它们有本质的区别

• 回溯——关键词【暴力试】。回溯本质上就是【暴力遍历】找到符合要求的路径，因此回溯的每一次纵向向下生长都是尝试性的，就是不断地试，一路生长下去直到得到一条合规的路径，而不在乎中间结点是否是最优的
• dp——关键词【最优解】。dp本质上是求解子问题的最优解，dp table的每一个值都是有目的地计算得到的最优解，而不像回溯那样盲目尝试

同时，它们也有相同的地方：
不管是回溯树的生长，还是dp table的填写，都要基于之前的状态。它们都是用来解决【前置状态依赖问题】的方法。

例：
给定一个二维矩阵，0表示不能种树，1表示可以种树，同时相邻位置不能种树，求一共有多少种种树的方法
分析：
1.在某个地方种树与否，会影响相邻位置是否能够种树，进而影响到更远的位置是否能够种树。不同规模的问题会产生相互影响。好了，到这里我们发现，每次考虑要不要种树，都需要基于之前的状态，那么要么回溯要么dp。而dp是解决最优解问题的，回溯是解决排列组合问题的，问多少种方法，明显是组合题，因此考虑用回溯
2.再回到问题，求的是组合的种数。事实上，我们不管从哪个位置开始，也不管以怎么样的顺序去逐个安排种树，最终种数都是一样多的。因此，我们给回溯树纵向生长的路径指定一个规则：不妨从第一个1的位置开始，按从左到右，从上到下的顺序，考虑每一个1的位置是否种树

## 处理输入输出
# 输入：
# 2 3  // 表示2*3的矩阵
# 0 1 1
# 1 1 0
# 输出：8
import sys
content = list(sys.stdin)
n, m = [int(ele) for ele in content[0].strip().split()]
matrix = []
for i in range(1,len(content)):
    temp = [int(ele) for ele in content[i].strip().split()]
    matrix.append(temp)
## 处理输入输出

res = 0

# 获得某位置的4个邻居位置
def getNeibor(position_i, position_j):
    global n, m
    for i_index, j_index in [position_i+1, position_j], [position_i-1,position_j], [position_i, position_j-1], [position_i, position_j+1]:
        if 0 <= i_index < n and 0 <= j_index < m:
            yield (i_index, j_index)

# 筛选出所有能够进行组合的位置（值为1的位置），用数组保存。如[(0,1),(0,2),(1,0),(1,1)]            
def getValidPositions(matrix, n, m):
    res = []
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                res.append((i,j))
    return res

# tree_path 已种树的位置
# choice_list 选择列表
# 通过这两个参数就可以描述visited_path, choice_list和target
def backTracking(tree_path, choice_list):
    global res
    # 到达target回溯出口
    if choice_list == []:
        res += 1
        return 
    
    # 当前位置
    a, b = choice_list[0]
    ## 当前状态下，问题面临2种选择：种或者不种
    # 检查当前位置的邻居是否种树了
    flag = False
    for nb in getNeibor(a, b):
        if nb in tree_path:
            flag = True
            break
    # 1.周围没有种树，在当前位置种树，带着种树的状态推动回溯树继续纵向生长
    if not flag:
        tree_path.add((a,b))
        # 递归
        backTracking(tree_path, choice_list[1:])
        tree_path.remove((a,b))
    
    # 2.当前位置不种树，带着不种树的状态推动回溯树继续纵向生长
    backTracking(tree_path, choice_list[1:])

validpositions = getValidPositions(matrix, n, m)
# 回溯的初始状态，tree_path = set()，choice_list = validpositions
backTracking(set(), validpositions)
print(res)

例
leetcode面试题46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

分析：本题我第一个想到的是回溯，回溯是比较自然的正向思维。但是回溯的话涉及到了对重复子问题的计算，后来又优化了一下改成了dp。从本题其实可以看到，回溯是深度优先以线（路径达到最深）推进；dp是以面推进，面对重叠子问题有优势

# 以下是dp解法，因为这里面存在重叠的子问题，且子问题间可以建立起状态转移关系
class Solution:
    # 按照dp解法模板
    # 1.确认dp[i]记录s[:i]字串的翻译方法，即以i-1位置结尾的字串的翻译方法
    # 2.状态转移方程：dp[i] = dp[i-1] + dp[i-2] or dp[i] = dp[i-1]
    # 3.基础状态dp[0] = 1, dp[1] = 1
    # 4.dp table的遍历方向：从左到右
    def translateNum(self, num: int) -> int:
        s = str(num)
        dp = [0] * (len(s)+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, (len(s)+1)):
            if 9 < int(s[i-2:i]) < 26:
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        # print(dp)
        return dp[-1]

另外，上面提到，这里的回溯涉及到对重复子问题的计算，因此属于【图形回溯】，那么我们做个中间结果备忘也可以做的

class Solution:
    def __init__(self):
        # 字典记录，避免多次运算
        self.d = {"":1}

    def translateNum(self, num: int) -> int:
        # 问总和，就是暴力
        return self.dfsHelper(str(num))
    
    def dfsHelper(self, s) -> int :
        # 递归出口
        if s in self.d:
            return self.d[s]
        
        res = 0
        # ele最多为e2位数
        for i in range(1,min(3, len(s)+1)):
            ele = int(s[:i])
            if ele > 25:
                break                
            else:
                res += self.dfsHelper(s[i:])
                if ele == 0:
                    break

        self.d[s] = res
        return self.d[s]