前言

經典回溯法

LeetCode 51. N-Queens

LeetCode 139. Word Break

LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another

組合與排列

LeetCode 46. Permutations

• 回溯法模板

LeetCode 78. Subsets

• 每個元素只能選取一次 ⇒ 指定 iterate 起始值

LeetCode 77. Combinations

LeetCode 90. Subsets II

避免產生重複的組合 ⇒ 對輸入進行排序，並且在 iterate 時將相鄰相同的元素直接忽略。

LeetCode 40. Combination Sum II

LeetCode 47. Permutations II

• 存在相同元素，要避免重複解 ⇒ 同時進行曾尋訪判斷以及相鄰元素相等判斷

將尋訪判斷調整成未尋訪過即略過，可將效率提升

LeetCode 39. Combination Sum

元素可以被重複選取 ⇒ 將遞迴的起始位置從 i+1 改成 i

小結

• 輸入元素不重複 且 最多使用一次 ⇒ 經典回溯解法

• 　輸入元素重複 且 最多使用一次 ⇒ 排除相鄰元素

• 輸入元素不重複 且 可使用無限次 ⇒ 遞迴起始值將 i+1 改成 i