DFS-leetcode Combination Sum I/I I

       深度優先搜尋(dfs)它是一個搜尋算法。第一次接觸dfs它應該是一個二進制樹的周遊内部，二叉樹預訂、序和後序實際上屬于深度周遊-first。在本質上，深度優先搜尋，周遊中則看到了更純正的深度優先搜尋算法。

       通常。我們将回溯法和dfs等同看待。能夠用一個等式表示它們的關系：回溯法=dfs+剪枝。是以回溯法是dfs的延伸。其目的在于通過剪枝使得在深度優先搜尋過程中假設滿足了回溯條件不必找到葉子節點。就截斷這一條路徑，進而加速dfs。

實際上，即使沒有剪枝，dfs在從下層回退到上層的時候也是一個回溯的過程，通常這個時候某些變量的狀态。

dfs通經常使用遞歸的形式實作比較直覺。也能夠用非遞歸。但通常須要借組輔助的資料結構（比方棧）來存儲搜尋路徑。

       以下通過leetcode上的兩個題目，來展示dfs的應用：

       題一  combination sum i，題目大意是這種：有一個正整數集合c，和一個目标數t（t也為正整數）。現從c中選出一些數，使其累加和恰好等于t（c中的每一個數都能夠取若幹次），求全部不同的取數方案。

       比如：c={2,3,6,7}  t=7

                  res={  [7],

                            [2, 2, 3] }

       題二  combination sum ii，與題一得差别是集合c中的每一個數最多僅僅能取一次，隻是c中能夠有反複的數。

       比如：c={10,1,2,7,6,1,5}  t=8

                  res={ [1, 7]

                           [1, 2, 5]

                           [2, 6]

                           [1, 1, 6] }

       題二能夠採用與題一類似的方法。可是因為題二中的每一個數僅僅能取一次，是以dfs函數中的for循環，i應從l+1開始，表示取下一個數。但這樣帶來的問題是，結果中會出現反複的取數方案。拿上面的樣例來分析：c中有兩個1能夠選，那第一個1和7是一種可選方案（1+7=8）。第二個1和7也是一種可選方案，依照上述算法。[1,7]會在結果中出現兩次。當然能夠對最後結果去重（假設用c++的話，sort->unique->erase能夠實作）。

不幸的是，這樣的解法會逾時。解決逾時的方案是不要将反複的方案增加到結果集中。也就避免了去重的工作。ac代碼例如以下：

關鍵代碼：

外層循環表示依次從c中選取一種數。内層的第一個循環表示c中這個數能夠取幾次，内層的第二個循環表示，假設不選上一個數的話。要恢複狀态。即把儲存的上一個數删除（增加了多少個，就删除多少個）。

版權聲明：本文部落格原創文章。部落格，未經同意，不得轉載。