20200804更新-回溯總結(jié)

回溯用于解決【1-n個元素的排列或組合問題】

• 1.未優(yōu)化的回溯算法需要遍歷完所有的情況，一共是n(n-1)(n-2)...1即n!種，時間復(fù)雜度O(n!)，是所有復(fù)雜度里面最大的。。。

• 2.將原集合的子集看做子問題，做了子集備忘的回溯每個子問題只需要計(jì)算一次，而子問題的個數(shù)是2^n， 時間復(fù)雜度O(2^n)，是所有復(fù)雜度里面正數(shù)第二大的。。。但是！這個復(fù)雜度也比O(n!)強(qiáng)多了。那么什么情況下可以使用【劃分成 2^n個子集】呢？【解具有局部無序的特征】當(dāng)只要求組間有序而組內(nèi)無序的時候，如假設(shè)序列ABCDE為所求，但實(shí)際上BACED\ABDCE也都滿足題意，AB一組，CDE一組，組間有序，組內(nèi)無序——換句話說，無論先A后B，還是先B后A，都能夠讓問題演進(jìn)到同樣的狀態(tài)。這一題的經(jīng)典例題就是#### 312. 戳氣球 and #### LCP 13. 尋寶 尋寶這題更難發(fā)現(xiàn)局部可無序這一潛在解特征。簡單來講就是，有M個機(jī)關(guān)要破解，機(jī)關(guān)之間的距離不同，找最短路徑。一拿到估計(jì)就想回溯，時間復(fù)雜度M!，要優(yōu)化一下。把M個機(jī)關(guān)映射到bitmap上面去，這樣子問題數(shù)量縮減成2^M， 而不同子問題間存在遞推關(guān)系，有遞推就可以DP了

• 3.【進(jìn)階】將原集合的子區(qū)間看做子問題，如集合[1,2,3,4,...,n]，def(0, n)作為當(dāng)前區(qū)間問題的解，則def(0, n) = best( def(0, i) + def(i, n), 0<=i<=n )。做了子區(qū)間備忘的回溯每個子問題只需要計(jì)算一次，而子問題的個數(shù)是n方，時間復(fù)雜度O(n^2)。這時實(shí)際上變成了更一般化的遞歸問題，無需狀態(tài)復(fù)原。見 leetcode312. 戳氣球，leetcode140. 單詞拆分 II
  這里對140單詞拆分進(jìn)行簡單分析

140. 給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，在字符串中增加空格來構(gòu)建一個句子，使得句子中所有的單詞都在詞典中。返回所有這些可能的句子。
     說明：
     分隔時可以重復(fù)使用字典中的單詞。
     你可以假設(shè)字典中沒有重復(fù)的單詞。

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

分析：
首先第一個想法肯定是暴力回溯，維護(hù)一個全局變量ans，當(dāng)回溯到底的時候做結(jié)果結(jié)算，時間復(fù)雜度O(n!)，n為s的長度
優(yōu)化一下，考慮到某個子字符串s’可能會被重復(fù)計(jì)算，也就是會出現(xiàn)重復(fù)子問題，我們通過hashtable把子問題的解記錄下來。具體地，對每一個字符串s，記錄它的字典解析結(jié)果，不可解析時記錄為[]，通過記錄實(shí)現(xiàn)剪枝，讓整個問題從回溯轉(zhuǎn)為記憶化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對應(yīng)的題目所求List[str]
    def dfs(self, s, wordDict):
        res = []
        # 遞歸出口。如果s為''，說明原始整個字符串已經(jīng)順利解析，返回非空的['']表示解析完畢；而返回[]則表示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:]不能進(jìn)行字典解析，整個s也就不能順利解析
                    for sentence in behind_res:
                        res.append(temp_word+(' '+sentence if sentence else ''))                                       
            self.res_dict[s] = res
        return self.res_dict[s]

小結(jié)：
當(dāng)問題等價(jià)于求一個排列或者組合時，往往可以考慮回溯，很大概率命中
關(guān)鍵點(diǎn)就在于識別出這是個排列組合問題
一般地，求順序的問題就是求排列，求子集的問題就是求組合

1、理解回溯

回溯就是回退，就是撤步/step back
舉個例子，尋寶：

回溯簡明圖解

2、回溯要點(diǎn)

• 回溯問題是樹形結(jié)構(gòu)問題

**事實(shí)上，回溯問題是一個樹形結(jié)構(gòu)的問題，因?yàn)椴粩嗲斑M(jìn)與回溯的過程會生長出一棵樹--我叫做前進(jìn)回溯樹(forward back tree, FBT)

• 回溯 = 深度優(yōu)先遍歷 + 狀態(tài)復(fù)原 + [剪枝] (根據(jù)具體問題判斷是否剪枝)

還是借用尋寶來理解

回溯樹形圖解

如圖，假設(shè)只有C點(diǎn)有寶藏，尋寶的路程如圖所示，其中黃色箭頭表示葉結(jié)點(diǎn)向上回溯

• 首先，人從起點(diǎn)到A到D，發(fā)現(xiàn)沒有寶藏，回退到A；
• 然后從A來到E處，發(fā)現(xiàn)沒有寶藏，又回退到A；
• 然后從A來到F處，發(fā)現(xiàn)沒有寶藏，又回退到A；
• 這時發(fā)現(xiàn)從A無論如何都到不了寶藏點(diǎn)，于是回退到起點(diǎn)
• ......如此反復(fù)
• 直到最終找到寶藏點(diǎn)C

由此我們可以看到，

• 對于尋寶問題形成的FBT樹，尋寶的過程遵循深度優(yōu)先遍歷，即先嘗試一條路走到黑，達(dá)不到目的再step back；
• 而step back，必須保證問題的各個狀態(tài)回到上一結(jié)點(diǎn)的狀態(tài)，即狀態(tài)復(fù)原，如從D點(diǎn)回到A點(diǎn)，問題的狀態(tài)需要恢復(fù)到A點(diǎn)的狀態(tài)

  狀態(tài)復(fù)原是回溯最最重要的一點(diǎn)

• 可剪枝。對于某些回溯問題，可以通過避免不必要的前進(jìn)（如只需找到一個解，那么找到之后就無需繼續(xù)搜索）、按結(jié)點(diǎn)值的大小順序構(gòu)造樹等操作來進(jìn)行剪枝，減少多余計(jì)算

3、回溯問題模板

將問題對應(yīng)一顆FBT樹，解決問題的過程就是不斷生長這棵樹的過程。如何生長這棵樹呢？

backtracking

backtracking(all_current_state)，all_current_state包括當(dāng)前已選路徑visited_path+當(dāng)前可選擇列表choice_list+回溯出口target

• 1.首先利用參數(shù)判斷當(dāng)前狀態(tài)下是否進(jìn)行結(jié)果結(jié)算
• 2.從選擇列表中選擇一個son結(jié)點(diǎn)，將問題狀態(tài) 更新為 son結(jié)點(diǎn)處對應(yīng)的問題狀態(tài)，表示選擇son結(jié)點(diǎn)后問題來到了son結(jié)點(diǎn)處?！靖卤仨毎ㄈ咳?xiàng)：visited_path+choice_list+target】
• 3.遞歸調(diào)用自己
• 4.遞歸返回后，進(jìn)行狀態(tài)復(fù)原，將前面第二步中修改的狀態(tài)改回去

def backTrack(visited_path, choice_list, result, target):
        # visited_path, choice_list, target 這3種參數(shù)是必須的
        # visited_path表示當(dāng)前的問題階段，choice_list表示當(dāng)前問題面臨的可選項(xiàng)，target出現(xiàn)表示問題無需繼續(xù)向下搜索，這時result用于結(jié)算可行解，
        # 遞歸出口
        if visited_path meets target:
            update result
            return
 
        # 嘗試結(jié)點(diǎn)每一個可能的選擇
        for c in choice_list:
            # 2.更新問題狀態(tài): 必須包含3項(xiàng)，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.狀態(tài)復(fù)原
            visited_path.remove(c)
            reset target

4、回溯解決的問題

很簡單，就2類，排列類問題和組合類問題。

• 排列類問題。每條路徑對應(yīng)一個排列，特點(diǎn)是路徑可以縱向自由生長，不遵循某種約束規(guī)律
• 組合類問題。在數(shù)學(xué)上，組合就是在排列的基礎(chǔ)上消序；對應(yīng)到回溯樹上，就是在回溯樹每次縱向向下生長的時候，必須遵循一定的規(guī)律，使得到整個路徑是按照特定規(guī)律生成的，從而實(shí)現(xiàn)消序

因此，更抽象地來看，回溯解決的問題是【求解自由路徑問題】和【求解有序路徑問題】

5、例子

給定一個沒有重復(fù)數(shù)字的序列，返回所有全排列
分析：
這是一個排列類問題，遍歷完整個回溯樹，葉子節(jié)點(diǎn)結(jié)算路徑即可

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表示，存放起點(diǎn)至當(dāng)前結(jié)點(diǎn)形成的排列
        choice_list 可用 used: List & nums: List求出
        target  用cur_result長度 == nums長度表示
        
        used: List 標(biāo)記序列中的某個元素是否被使用，長度與nums一致。
        result: List 用于存放給定序列的所有全排列                
        '''
        
        # 回溯出口
        if len(cur_result) == len(nums):
            # 結(jié)果結(jié)算
            print('result update')
            result.append(cur_result.copy())
            return
        
        for i in range(len(used)):
            # 如果元素未被使用，這些元素組成模板代碼中的choice_list
            if not used[i]:
                # 更新狀態(tài)：更新cur_result和used[i]，target不變不用修改
                cur_result.append(nums[i])
                print('cur_result is %s' % str(cur_result))
                used[i] = True
                # 對結(jié)點(diǎn)進(jìn)行操作，這里是進(jìn)行遞歸操作
                self.backTracking(cur_result, used, nums, result)
                # 遞歸結(jié)束，恢復(fù)原來的狀態(tài)
                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]
]

有了本題的基礎(chǔ)，我們可以給出求排列組合的一般形式：
以升序形式給定n個數(shù)，并指定一個k(0<k<=n)，求這n個數(shù)中所有可能的k個數(shù)的排列以及組合

顯然，求n個數(shù)中所有k個數(shù)的排列，只是在上題的基礎(chǔ)上，限制了樹的深度。當(dāng)len(visited_path)==k時，停止生長，即為target
而求n個數(shù)中k個數(shù)的所有組合，只需要在求排列的基礎(chǔ)上進(jìn)行消序操作即可。例如[1,2,3]和[2,1,3]是2個排列，但屬于同一個組合。因此只需要選取排列中特定的一個作為組合結(jié)果，選升序的排列或者降序的排列都行。這也就是說，路徑必須是升序或者降序的

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]:
                    # 如果求組合，加入這句判斷，通過形成升序的路徑進(jìn)行消序
                    if cur_result and nums[i] < cur_result[-1]:
                        continue
                    # 修改狀態(tài)，visited_path + choice_list，target一直不變
                    used[i] = True
                    cur_result.append(nums[i])
                    # 遞歸
                    self.backTracking(nums, used, cur_result, result, k)
                    # 狀態(tài)恢復(fù)
                    used[i] = False
                    cur_result.pop(-1)

趁熱打鐵
leetcode 40.
給定一個數(shù)組candidates和一個目標(biāo)數(shù)target，找出candidates中所有可以使數(shù)字和為target的組合，并且candidates中的每個數(shù)字在每個組合中只能使用一次

說明：
所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。
解集不能包含重復(fù)的組合。
示例1:
輸入: candidates =[10,1,2,7,6,1,5], target =8,
所求解集為:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
原鏈接
分析：
看題，直接告訴我們，求的是【組合】。那么就需要設(shè)定路徑的縱向生長順序或者說生長規(guī)律。因此，這個規(guī)律可以是，將一個數(shù)num納入路徑后，再縱向生長的路徑只能由num后面的數(shù)組成（這是萬能的求組合的路徑縱向生長規(guī)律）。這里有個小tip，我們選擇將candidates先做個升序排序，這樣一旦我們找到一個符合條件的路徑，就可以進(jìn)行剪枝。

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
        
            
    # 回溯函數(shù)    
    def backTracking(self, part_result, choice_list, target, result):
        # part_result 表示 visited_path
        # choice_list 表示 choice_list
        # target

        ## 到達(dá)葉子節(jié)點(diǎn)，返回True來實(shí)現(xiàn)剪枝。因?yàn)閠arget < 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個狀態(tài)。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)
                # 狀態(tài)復(fù)原
                target = temp_target + part_result.pop()
                # 根據(jù)break_flag進(jìn)行【橫向剪枝】
                if break_flag:
                    break
            else:
                continue
        ## 不是回溯樹的葉子節(jié)點(diǎn)，【返回false表示不橫向剪枝】
        return False                

遞歸返回后必須馬上進(jìn)行狀態(tài)復(fù)原！?。。。。。。。。。?！

還有 leetcode 51. N 皇后
N皇后問題，也是需要不斷地嘗試，當(dāng)皇后不能以合法的位置放置時，回溯進(jìn)行新的嘗試，直到找到合法的放置方法

對于一個n X n的棋盤，我們希望從上往下逐行合法地放置一個皇后
那么，

• 維護(hù)一個queen_pos作為階段性結(jié)果集，保存當(dāng)前已經(jīng)放置好的皇后的位置
• 維護(hù)一個dict，dict[pos] > 0 表示當(dāng)前情況下pos位置非法，該位置屬于dict[pos]個皇后的勢力范圍，現(xiàn)在不可以放置新皇后；如果dict[pos] == 0，則可以在此放置皇后
  我們每放置一個皇后，就把行、列和兩個斜線上的所有位置的字典值+1；每次回溯移除一個皇后，就把相應(yīng)的字典值-1
  理清思路后，代碼也可以清晰地寫出

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 設(shè)置好規(guī)則，【dfs】暴力嘗試所有解。如果能夠dfs到第n層的，說明整個路徑上的皇后位置合法，納入結(jié)果集。
        # 用queen_pos list記錄可行的皇后位置；用字典invalid_pos記錄當(dāng)前不可放置的位置，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):
            # 已經(jīng)到整個棋盤的n行，說明0-n-1行都放好了，結(jié)算并返回
            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)
                    # 狀態(tài)復(fù)原
                    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、再進(jìn)階一下

在上面的問題中，問題起點(diǎn)都是唯一的，即只有一個根結(jié)點(diǎn)，只產(chǎn)生一棵FBT樹。但有時候，會存在多個問題起點(diǎn)，那么我們就需要對應(yīng)產(chǎn)生多棵FBT樹

例如leetcode79題：
給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。
單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復(fù)使用

示例:
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開頭，那么搜索的起點(diǎn)可以是board[0][0]，也可以是board[2][0]，起點(diǎn)有多個。對每一個起點(diǎn)，都要進(jìn)行嘗試

當(dāng)訪問完某個字符時，問題下一步可以去的位置是這個字符的上下左右位置，但注意，上下左右中溢出board邊界的位置和已經(jīng)訪問過的位置要剔除，剔除后的位置就是可以去的一個個可選項(xiàng)

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結(jié)合可求出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的狀態(tài)
                visited_path.append(pos)
                new_all_neibor = self.getNeibor(board, pos)
                self.backTracking(visited_path, board, new_all_neibor, target[1:])
                # 改回visited_path的狀態(tài)
                visited_path.pop()
                if self.res:
                    return

7.進(jìn)一步思考，回溯與dp的不同之處

回溯和dp看似有點(diǎn)相似，一個自頂向下，一個自底向上，但它們有本質(zhì)的區(qū)別

• 回溯——關(guān)鍵詞【暴力試】。回溯本質(zhì)上就是【暴力遍歷】找到符合要求的路徑，因此回溯的每一次縱向向下生長都是嘗試性的，就是不斷地試，一路生長下去直到得到一條合規(guī)的路徑，而不在乎中間結(jié)點(diǎn)是否是最優(yōu)的
• dp——關(guān)鍵詞【最優(yōu)解】。dp本質(zhì)上是求解子問題的最優(yōu)解，dp table的每一個值都是有目的地計(jì)算得到的最優(yōu)解，而不像回溯那樣盲目嘗試

同時，它們也有相同的地方：
不管是回溯樹的生長，還是dp table的填寫，都要基于之前的狀態(tài)。它們都是用來解決【前置狀態(tài)依賴問題】的方法。

例：
給定一個二維矩陣，0表示不能種樹，1表示可以種樹，同時相鄰位置不能種樹，求一共有多少種種樹的方法
分析：
1.在某個地方種樹與否，會影響相鄰位置是否能夠種樹，進(jìn)而影響到更遠(yuǎn)的位置是否能夠種樹。不同規(guī)模的問題會產(chǎn)生相互影響。好了，到這里我們發(fā)現(xiàn)，每次考慮要不要種樹，都需要基于之前的狀態(tài)，那么要么回溯要么dp。而dp是解決最優(yōu)解問題的，回溯是解決排列組合問題的，問多少種方法，明顯是組合題，因此考慮用回溯
2.再回到問題，求的是組合的種數(shù)。事實(shí)上，我們不管從哪個位置開始，也不管以怎么樣的順序去逐個安排種樹，最終種數(shù)都是一樣多的。因此，我們給回溯樹縱向生長的路徑指定一個規(guī)則：不妨從第一個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)

# 篩選出所有能夠進(jìn)行組合的位置（值為1的位置），用數(shù)組保存。如[(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 選擇列表
# 通過這兩個參數(shù)就可以描述visited_path, choice_list和target
def backTracking(tree_path, choice_list):
    global res
    # 到達(dá)target回溯出口
    if choice_list == []:
        res += 1
        return 
    
    # 當(dāng)前位置
    a, b = choice_list[0]
    ## 當(dāng)前狀態(tài)下，問題面臨2種選擇：種或者不種
    # 檢查當(dāng)前位置的鄰居是否種樹了
    flag = False
    for nb in getNeibor(a, b):
        if nb in tree_path:
            flag = True
            break
    # 1.周圍沒有種樹，在當(dāng)前位置種樹，帶著種樹的狀態(tài)推動回溯樹繼續(xù)縱向生長
    if not flag:
        tree_path.add((a,b))
        # 遞歸
        backTracking(tree_path, choice_list[1:])
        tree_path.remove((a,b))
    
    # 2.當(dāng)前位置不種樹，帶著不種樹的狀態(tài)推動回溯樹繼續(xù)縱向生長
    backTracking(tree_path, choice_list[1:])

validpositions = getValidPositions(matrix, n, m)
# 回溯的初始狀態(tài)，tree_path = set()，choice_list = validpositions
backTracking(set(), validpositions)
print(res)

例
leetcode面試題46. 把數(shù)字翻譯成字符串
給定一個數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l(fā)”，……，25 翻譯成 “z”。一個數(shù)字可能有多個翻譯。請編程實(shí)現(xiàn)一個函數(shù)，用來計(jì)算一個數(shù)字有多少種不同的翻譯方法。
示例 1:
輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

分析：本題我第一個想到的是回溯，回溯是比較自然的正向思維。但是回溯的話涉及到了對重復(fù)子問題的計(jì)算，后來又優(yōu)化了一下改成了dp。從本題其實(shí)可以看到，回溯是深度優(yōu)先以線（路徑達(dá)到最深）推進(jìn)；dp是以面推進(jìn)，面對重疊子問題有優(yōu)勢

# 以下是dp解法，因?yàn)檫@里面存在重疊的子問題，且子問題間可以建立起狀態(tài)轉(zhuǎn)移關(guān)系
class Solution:
    # 按照dp解法模板
    # 1.確認(rèn)dp[i]記錄s[:i]字串的翻譯方法，即以i-1位置結(jié)尾的字串的翻譯方法
    # 2.狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[i-1] + dp[i-2] or dp[i] = dp[i-1]
    # 3.基礎(chǔ)狀態(tài)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]

另外，上面提到，這里的回溯涉及到對重復(fù)子問題的計(jì)算，因此屬于【圖形回溯】，那么我們做個中間結(jié)果備忘也可以做的

class Solution:
    def __init__(self):
        # 字典記錄，避免多次運(yùn)算
        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位數(shù)
        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]