Leetcode 题型分类 1）search: DFS/Backtracking and BFS

蜗牛速度缓慢刷题中，归纳一下近期刷的 search: DFS/Backtracking and BFS 子分类，便于总结模版。之后希望有毅力持续更新其他分类(下一个准备刷tree, 然后graph)。  huahua 的https://zxi.mytechroad.com/blog/leetcode-problem-categories 是我的reference.
a.) Combination With Duplicates:
39. Combination Sum
40. Combination Sum II
90. Subsets II
254. Factor Combinations

b.) Combination Without Duplicates:
77. Combinations
216. Combination Sum III
78. Subsets
1239. Maximum Length of a Concatenated String with Unique Characters

c.) Combination:
17. Letter Combinations of a Phone Number
784. Letter Case Permutation
797. All Paths From Source to Target
967. Numbers With Same Consecutive Differences
377. Combination Sum IV (DP not backtracking)

d.) Permutation With Duplicates:
46. Permutations
526. Beautiful Arrangement
357. Count Numbers with Unique Digits

e.) Permutation Without Duplicates:
47. Permutations II
996. Number of Squareful Arrays

f.) Combination/Permutation with BIT:
89. Gray Code

g.) Partition:
93. Restore IP Addresses
131. Palindrome Partitioning
1593. Split a String Into the Max Number of Unique Substrings
842. Split Array into Fibonacci Sequence
291. Word Pattern II
698. Partition to K Equal Sum Subsets

h.) DFS1 backtracking:
22. Generate Parentheses
301. Remove Invalid Parentheses

i.) DFS2 fill matrix backtracking:
37. Sudoku Solver
51. N-Queens
52. N-Queens II

j.) DFS3 word search backtracking:
79. Word Search
212. Word Search II

k.) DFS4 search:
241. Different Ways to Add Parentheses
282. Expression Add Operators

l.) BFS search:
127. Word Ladder
126. Word Ladder II
752. Open the Lock
433. Minimum Genetic Mutation

总结的和我的思路惊人一致! 我也正在by topic刷. 期待更新!

太有用啦！给楼主加米了 我也在刷这个类型的 感觉还是有不少难题的

喜欢您的分类思路！蹲更新呀～

lz的思路好棒！

另外想问一下lz是怎么区分或怎么理解backtracking和DFS的呢？

Husky_wang 发表于 2022-2-7 16:12
lz的思路好棒！

另外想问一下lz是怎么区分或怎么理解backtracking和DFS的呢？

我理解的也还不够深刻，我得重新刷刷思考🤔。 我在leetcode 里看到有个回答很符合我的理解： “In Backtracking, we need to restore previous state of visited node, by making visited=false, after exploring current path whereas in DFS the state of the node remains same after a path is explored so that it will not be explored again. Or we can say that pure DFS is a variant of backtracking in which state of visited nodes are not restored, and this variant is only useful for problems related to searching (reachability, etc) and not for problems involving pattern finding, for which we need to use the usual backtracking tree pruning algorithm.” （https://leetcode.com/discuss/gen ... -depth-first-search）。 我之后更新一下graph 的 subcategory, graph 里的dfs 和backtracking 比较一下大概就能感觉出上边说的那个意思。

lisawangqian 发表于 2022-02-10 08:03:47
我理解的也还不够深刻，我得重新刷刷思考。 我在leetcode 里看到有个回答很符合我的理解： “In Backtracking, we need to restore previous state

还想请问下你觉得如果把这上面的分类题目刷完的话是否可以对dfs或backtrack有一个更深刻的理解以及面对新题目的时候有举一反三的能力呢？