這題是 39. Combination Sum 的進階,給定一個 array 和 target ,找出 candidates 中所有可以使數字和為 target 的組合,但 candidates 中的每個數字,在每個組合中只能使用一次。對比 39. 中的數字是可以重複使用,這題是不能重複使用的,但兩題本質沒有區別,依然是使用 DFS 和 backtrack 思想求解。寫到現在其實已經有感覺到一定的模板了,但多多比較與其他 backtrack 題型的差異才是最重要的。

這題是 39. Combination Sum 的進階,給定一個 array 和 target ,找出 candidates 中所有可以使數字和為 target 的組合,但 candidates 中的每個數字,在每個組合中只能使用一次。對比 39. 中的數字是可以重複使用,這題是不能重複使用的,但兩題本質沒有區別,依然是使用 DFS 和 backtrack 思想求解。寫到現在其實已經有感覺到一定的模板了,但多多比較與其他 backtrack 題型的差異才是最重要的。
這題給了一個 array of distinct integer 以及目標總和 target , 求用此 array 來組成目標數字的所有組合。像這種要求返回所有符合要求解的題目,基本都是要利用到遞迴,類似的題目有 Subset 、 Permutation 、 Combination 等等,解題套路都是使用 DFS 和 Backtrack 來求得答案。
之前解題利用了交換 nums 裡面的兩個數字的方式,這次換另一種寫法,做出一個 inner list 收集可能的結果。基本解題思想都還是 Backtracking ,故把 leetcode46 和 leetcode47 重新解答一遍。
是經典的 46. Permutations 的進階版,現在數字會有重複(duplicate) 。這邊一樣使用 Backtrack 來求解。從數學上來說,
n
個 element ,且將相同的事物歸為一組, 可歸成 k 組, 且每組有m_i
個,其 Permutation 一共有n!/(m_1!m_2!...m_k!)
種排序,為高中數學題中,需要思考下的題目;用程式模擬這個過程也有難度,故被歸類在 Medium 等級。
是一道經典 distinct integers 的全排列問題,這邊使用 Backtrack 來求解。從數學上來說,n 個 element 的 Permutation 一共有 n! 種排序,思考起來算蠻簡單的,但要用程式模擬這個推導過程,卻是有點難度的,因此被歸類在 Medium 等級。
Backtrack 是 DFS 的一種形式,基本寫法類似於 TOP DOWN DFS,處理方式就是所謂的窮舉法,將所有可能的結果都找出來;每一個結果都實際看看這樣。換個角度來說,其實這個過程就如同在樹上遍歷 (Tree Traversal) ,而普通的 DFS 是不需要回溯狀態的。 Backtrack 強調了狀態回溯。