【LeetCode】Backtracking

Backtracking：通常是用在需要纪录路径的 DFS 时。

1. 往前搜寻，发现目前的元素不符合条件，就退回去上一步，并恢复原状，再去做别的尝试。
2. 当纪录的路径是想要的结果时（例如 DFS 深度），记录下来，退回上一步。

常见的 itertools 中会用到的 combination, permutation 还有 subset 的实作。
都可以试试看用 backtracking 做，当然也可以用 DP。
77. Combinations
46. Permutations
78. Subsets

对於一般新手来说，一开始可能比较难理解这部分的递回，或是容易把不同的解法搞混。

常见错误：append 还是 +=

在写 subsets 时，我一开始不太会构建我的递回，
虽然知道要有 base case，要有递回的部分，和 return，但常常还是写得乱七八糟。
尤其是对於阵列的元素到底要 append 还是用 +=？现在拿到的 list 有可能为空吗？等等
要仔细想清楚。
这个错误其实也不是特别针对 backtracking，而是要纪录状态或元素时可能会不小心搞错的。

以 subsets 这类型题目为例：

1. 如果是呼叫了原来的 function，return 的型态就很确定，一定是 2d array
   例如这样：

 def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]
        l = self.subsets(nums[:-1])
        ans = [term + [nums[-1]] for term in l] + l
        return ans

2. 如果是 dp，要基於一个变数去增加的话
   这个 ans 也是个 2d array，取出来的 e 则是一个 list。
   e.append(nums[i]) 会回传 None，所以只能用 +

ans = []
for i in range(len(nums)):
    ans += ([[nums[i]]] + [[nums[i]] + e for e in ans])

3. 或是用 backtracking 产生各种长度的 combination
   因为 cur 是一个 list，所以 append 之後传已经加完新元素的 cur 进去递回中。

def backtrack(first = 0, cur):
    if len(cur) == k:  # 到达深度 k
        output.append(cur[:])
        return
    for i in range(first, n):
        cur.append(nums[i]) 
        backtrack(i + 1, cur)
        cur.pop() # 恢复状态再去加下一个数字

4. 还有各种其他写法
   我每次写都写出不一样的、奇形怪状的东西ＸＤ
   所以主要还是要练习能够快速判断自己在干嘛，并注意 append 不会回传东西，+ 可以直接得到合并好的阵列。

对於 backtracking，
只要知道自己在干嘛，顺着思路，
自然而然在某个地方就是需要做状态的恢复，
才能去试试下一条路。
因为关心的不只是最後找到的元素，而是整条 dfs 的路线。
对於 combinations 来说，这条路线就是其中一个合法的 combination，只要找到用完全部元素的那条（也就是到达最深的深度）就纪录、return、恢复前一动。
对於 matrix 中找单字（昨天提的 word search） 来说，这条路线就是目前找到的 substring，只要发现下一步找到的元素不能组成 target，就恢复上一动；如果找到了，就回传 true