理解backtracking

[y4h2]

backtracing的本质还是dfs

可以从常见的简单的dfs进行推导。

简单的dfs例子200. Number of Islands, 地图类的dfs的方案是从当前的点(i, j)向四周(i+1, j), (i-1, j), (i, j+1), (i, j-1)移动，对于下一个点一般会有条件约束，

而对于46. Permutations从当前点(i, j)向其他所有的点移动，限制是不能取重复的点

[y4h2]

tree的遍历类似于dfs的特殊情况。preorder, inorder, postorder相当于对于stack进出栈的不同讨论。
tree是分别处理左右子树， backtrack是处理for循环

[y4h2]

1079. Letter Tile Possibilities
通过Counter来避免生成重复值

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        counter = Counter(tiles)
        self.result = 0
        
        def backtracking():
            self.result += 1
            for i in range(26):
                c = chr(ord('A') + i)
                if counter[c] == 0:
                    continue

                counter[c] -= 1

                backtracking()
                counter[c] += 1
                
        backtracking() 
        return self.result

也可以通过对字符串排序，然后控制index来避免重复