• 给出所有方案
• 给出最优/长/trueOrFalse 方案（大部分与DP 结合）

O(答案个数 * 构造每个答案的时间复杂度)

• 怎么解决DFS？ 不是排列就是组合

DFS(node){
   if(!node)
       return;
   foo(node);
   for(each in node adjacents){
      if(visited[each] = false)         
         DFS(each);
         visited[each] = true;
    }
}

1. Backtracking 常见类型：排列/组合/recursion/non-recursion/graph 1.1 给出所有方案 -> find all same length solution matching criteria 1.2 全子集问题（Subset）-> find all various length subset 1.3 排列式搜索(Permutation-based) 1.4 2D 搜索 1.5 top down, 结果取决于结果，对于主结果遍历， 加入主结果中，多可用memo优化 1.6 Greedy: 先减少candidates个数，在查找 1.7 切分: 每次前进符合条件的步数，再dfs，经常加上memo
2. Recursion
   • Traverse( top -> down)
   • DivideConquer( bottom -> up)
3. Iteration
4. 基于树的深度优先搜索(Tree-based)
5. 基于图的深度优先搜索(Graph-based)
   • 用STACK 实现
   • 非递归怎么办？ 必“背”程序: 只考preOrderTravese/permutation/expression expand/iterator (见Data Structure)
   • Word 四兄弟(Word Break/Word Ladder/Word Search/Word Pattern)
   • 拓扑排序

• Memomization/DP 注：此时结果由方程返回，而不是在全局变量
• 提前prune避免TLE（e.g currScore 已经 > bestMinScore)
• 可以bitstring或0/1string来表示memo的state
• python中的int()函数 == floor()
• 去重： if i > 0 and A[i] == A[i-1]: continue
• 为了避免代码重复，可以将visit的赋值放于dfs的一开始并在函数最后恢复原值。

** 在有重复input的情况下，避免重复ouput:

39. Combination Sum 有重复，可选多次

A.sort() # 需先排序
def combinationSum(idx, temp, total): 
    if total == target:
        res.append(temp[::])
        return
    elif total > target:
        return
    for i in range(idx, len(A)):
        for i > 0 and A[i] == A[i-1]: continue # 只选重复出现的第一个元素 ## ATTENTION HERE!!!
        temp.add(A[i])
        helper(i, temp, total + A[i])
        temp.pop()

时间复杂度O（N^(T/M), 空间复杂度O（T/M), 其中T = target， M = min(candidates)，N = len(candidates)

40. Combination Sum II 有重复，只可选一次

A.sort() # 需先排序
def combinationSum(idx, temp, total): 
    if total == target:
        res.append(temp[::])
        return
    elif total > target:
        return
    for i in range(idx, len(A)):
        for i > 0 and A[i] == A[i-1]: continue # 只选重复出现的第一个元素 ## ATTENTION HERE!!!
        temp.add(A[i])
        helper(i + 1, temp, total + A[i])  ## ATTENTION HERE!!! ONLY Difference with ComibniationSumI
        temp.pop()

17. Letter Combinations of a Phone NumberO（n4^n)
22. Generate Parentheses 2305. Fair Distribution of Cookies加入early stopping条件，若还没有分到饼干的小朋友数量>剩余饼干数 -> 提前终止
37. Sudoku Solver用rows[9][9], cols[9][9],blocks[9][9]记录每行/列/块中数字1-9是否已出现，对每个格子dfs(遍历1-9),填好后，dfs(i, j+1),若已到最后一列，dfs(i+1, j)\

51. N-Queens用file[], upperLeftDiag[i-j], upperRightDiag[i+j]来记录是否出现过
52. N-Queens II完全同51
77. Combinations
89. Gray Code每次改一个bit, dfs, 因为只需返回一个有效路径，故若dfs返回路径，能返回该路径
351. Android Unlock Patternsdfs, 用bit表示当前状态，无需memoization
216. Combination Sum III完全同40， O（k*p^k)
254. Factor Combinationsmemo[i]存可以组成i的combination
282. Expression Add Operatorsdfs(i, total, prev, temp)，其中temp中保存算式，处理乘法时，剪掉prev, 再加上prev*curr，prev只在乘法时会用到，每步dfs时，curr成了prev。
1601. Maximum Number of Achievable Transfer Requests类似于40.combinationSum, 但加入的条件为move[]全都为0
399. Evaluate Division用mp[a][b]=a/b， visited set， dfs\

756. Pyramid Transition Matrix对于每一行dfs,建立下一行时，可以将所有符合条件的top放在一起，使用，itertools.product(*tops)产生cartesian product, 即为下一行\

Max Area of Island (handle the duplicates through changing the original value to be zero.)

Decode String

Matchsticks to Square (This is actually solved by backtracking, NP complete. By adopting several tricks, NP problem can be solved much faster: 1. start from larger number first, so that those unqualified can be eliminated earlier. 2. avoid solving duplicated cases, for example, both sides have length 3, target length 5, then only need to add new element to one side and skip the similar operation for the second side. A related classic problem: (https://en.wikipedia.org/wiki/Partition_problem))

Longest Increasing Path in a Matrix (Simply DFS recursion with memorization.)

Walls and Gates Can also be solved by DFS. The key is to start searching from gate.

Robot Room Cleaner Simply DFS from the starting node while keep tracking of the visited status of node position relative to the starting point.

delete-node-in-a-bstClassic Approach to remove node in BST, 3 cases. find-leaves-of-binary-tree

Recursion/BackTracking

binary-tree-longest-consecutive-sequence

android-unlock-patterns

Solved by DFS, not sure DP is going to help.

expression-add-operators

Traditional backtracking with no memorization trick, but the hard part is to handle multiply, using previous presum - lastFactor + lastFactor * multiplier, and then set lastFactor * multiplier as the new multiplier.

factor-combinations

I spent a lot of time of this question. So stupid.

465. Optimal Account Balancing 用backtracking 逐个消去netValue of each account O(n!)) 问题可以简化为一堆unsolved balance[-2,1,4,0,3, ...],找到min steps to merge nonzeros until one one nonzero left. backtracking from the start index, for j in [startIdx + 1, end]: debts[j] += debts[startIdx]; cnt = min(cnt, 1 + dfs(startIdx + 1)), debts[j] += debts[startIdx]. 导致path cnt不同的原因在于当debts[j]恰好变成0时，我们可以跳过。故每次dfs开始时，我们移动startIdx到第一个不为0的位置。 '还是不大懂！！！`\

• which means any search along the path is a valid result and need to be added to the final result. Typical question is find all subset. Here there is no target, so each search along the path is added to the result.
• 和1.1唯一区别在于dfs一开始，不进行条件判断，全都加入res， 之后的for loop dfs和1.1完全相同

78. Subsets 90. Subsets II同样的去重方法：if nums[i] == nums[i-1] and i > idx : continue

leetcode #39 combination sum leetcode #46 Permutation

This can be elegantly solved by swapping the current index element and later element, which definitely beat the way of insert and erase element from the previous construction.

leetcode #77 Combinations leetcode $46 Permutation Each iteration insert indexed element to all possible positions of temp, until index reaches the end.

leetcode #78 Letter Combinations of a Phone Number

leetcode# 131 Palindrome Partition

leetcode# 79 word search
leetcode# 93 Restore IP Address
leetcode# 51 N Queens
leetcode# 37 Sudoku Solver (Here, the idx are two dimensional, and the element to try in the for loop is the number to be put at the position).
leetcode# 282 [Expression Add Operator] (https://leetcode.com/problems/expression-add-operators/description/)

leetcode 301 Remove Invalid Parenthesis This problem seems no harder at all at first glance. But the key point is to find the minimal removal results. To do this, simply compare with the current minimal removal steps at eh end of backtracking and update is not enough. As it can potentially store all the possible results. A smart way to handle this is simply find result which only removes the extra parenthesis. For example, if we have two more ')' in the original expression, then when we not include one ')' in the path, then we are essentially reduce the extra right parenthsis by one. Oh the other hand, if we not include the non-extra parenthesis, than it is definitely not the optimal solution, and we can stop the search on the path immediately; Another issue we need to handle is the duplicates in the path, for the solution i submit, it is simply handled by a set. It is something to be further improved. It seems to me, not sure if it right, the reason why leftRem and rightRem are both kept, instead of one single number is to for early eliminiating. when two rem variables can stop immiediately when leftRem or rightRem goes negative, however, if just use one number, then the negative value simply means extra right and vise versa.

partition-to-k-equal-sum-subsetsCan use binary to represent if ith has been included.

Cracking the Safe

It can be proved the problem is a eular path problem, while equivalent to DFS. Treat every node as a combination, and the the neighbouring nodes are the same (n-1)suffix of fromNode = (n-1)prefix of ToNode. We just need to visit all nodes.

lexicographical-numbers

this can be solved constructing from the bottom by adding the first digit, and the dfs(remaining digit + first digit * 10).

• In this situation, only need to sort the candidates first and no need to recurse the duplicates except the first appearance. The following elements are considered only if all previous same value have been added to the path. This is because the function skip the first appearance and contain the second (foo(candidates, firstAppearIdx + 1, temp, res), where temp doesn't contain the fist appearance) will be included in the function contains the first appearance and skip the second element(foo(candidates, firstAppearIdx + 1, temp, res), where temp contains the first appearance). If in the second level, the second element is not added to the temp, then it will be the same as the first case.
• permutation dfs() 参数不传指数，每次for loop从0-n, 但是需要visited set来记录哪些被访问过。

46. Permutations 47. Permutations IIonly insert element before the duplicated ones, once for(k) once k != 0 and nums[i] == temp[k-1] => break. consider insert [2] to [2,1], we will only insert at position 0. if position 1, [2, 2, 1] will be the same as position 0; if position 2, [2, 1, 2] will already be included when inserting 2 to [1, 2] at position 0.

A.sort()
def dfs(temp, visited):
    if len(temp) == len(A):
        res.append(temp[::])
        return
    for i in range(len(A)):
        if i in visited: continue
        if i > 0 and A[i] == A[i - 1] and (i - 1) not in visited: continue # 只选重复出现的第一个元素 ## ATTENTION HERE!!!
        visited.add(i)
        temp.append(A[i])
        dfs(temp, visited)
        visited.remove(i)
        temp.pop()
    return

267. Palindrome Permutation II用counter找到出现奇数次的字母，剩下的字母用dfs组建左半部分
294. Flip Game II用memo[state]记录下state下的胜负，不用记回合
679. 24 Gamedfs中每次挑两个数字， 由加减乘除分别产生新的数，和原来其他数组成新的list，-> dfs
1799. Maximize Score After N Operations用bitmask表示state, memo[state]表示当前状态下，将来最多还能有多少分数，dfs中for loop 挑两个未访问的数字a, b， idx*gcd(a,b) + dfs(idx + 1, newState),memo status中无需idx的信息，因为state中已含\

• 主函数中对每个格子dfs
• 为了避免代码重复，可以将visited的赋值放入dfs一开始和结束

79. Word Searchit is almost brute force by matching the head and compare one by one.
212. Word Search IIThis problem is solved by backtracking on trie. All the words are used to build a trie, while during the backtracking, each starting board value is compared with the trie, and backtracking if match; To avoid return duplicated words, once a word is find, remove the endOfWord label for this word in the trie.O(M(4*3^(where M is the number of cells in the board and L is the maximum length of words.), space O(N),where N is the total number of letters in the dictionary.
980. Unique Paths III访问后visited[i][j]=True\

1240. Tiling a Rectangle with the Fewest Squares看成[height]*m个column， 每步dfs找到最低height, 遍历所有可能填入方块长度， backtracking， 直至height全部等于n
126. Word Ladder II先用bfs得到每个单词到终点的距离，再用dfs\

93. Restore IP Addresses 切分 131. Palindrome Partitioning切分 140. Word Break IISolved with DFS + memorization of {suffix startIdx: possible combination}. 若用memo, 结果必须通过return返回。 Can be also solved by DP with dp[i] represent the possible combinations for s[:i]. Time and Space Complexity for both dfs and dp are O(n2^n).
291. Word Pattern II用{patternLetter:substr}记录对应，若letter不在map中，对每个letter遍历所有可能性\

95. Unique Binary Search Trees IIdivide & conquer, 用memo
1306. Jump Game IIIdfs + visited
332. Reconstruct Itineraryeular路径问题；若正序加入，若遇到终点，会陷入deadend， 故确保其所有邻居加入path后，再加入orig.不是很懂！！
472. Concatenated Words可用dp或bfs， 都为O(n*L^3);dfs + memo, for j in range(len(word)), 1) 判断dfs(w[:i]) & w[i:]in wordSet 2) 判断dfs(w[i:]) & w[:i]in wordSet 3)w[:i]in wordSet & w[i:]in wordSet\

216. Combination Sum III建立denotate的dictionary, 对于每个炸弹，重制visited=False,dfs后数由多少个被visited
1048. Longest String Chainworking backword, 无需建立neighbor graph, 从每个单词开始dfs， 看起去掉当中字母后是否在set中,memo[word]记录以word为终点组成string chain的最长值
301. Remove Invalid Parentheses先判断需要移除几个（, 几个）, 再用dfs分别讨论保留/移除（和）
631. Design Excel Sum Formulaset()时O（1）操作，cell[i][j]中存val或list of dependency; get时，若cell[i][j]中存有list，则对每个元素分别用get; dependency在sum时设置\

• 见树的iterative解法 data structure: tree
• 用stack实现

364. Nested List Weight Sum IIstack中存（val, curr depth)，running_total = curr_depth * val, 同时统计total_val, max_depth, res = (maxDepth + 1) * total - running_total\

见BFS

concatenated words

A follow up version of word break, sort the word by length, consider if each word can be formed by all words ahead of it.

number-of-distinct-islands用tuple of points along the path 记录dfs的路径， 相同形状的岛应该有相同的路径

见BFS Reconstruct Iteneary (Famous Hierholzer's algorithm to solve Eularian Path, see wiki. Basically, find a valid path first until can no longer goes further, and find nodes with extra loop backward, add the loops to the path.)

parse-lisp-expression

用list of dictionary(symbol ->val) 来记录每一层。

basic-calculator-iv

两道题很像，其中很重要的parse function可以share,剩下的区别就在于lisp exp用[{}]来记录每一层的变量，而这里变量是不变的，但用stack来处理乘法，另外，每次recursion返回dictionary{symbol:coeff}.