定義
Depth First Search (DFS): an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
要點：樹或者圖搜索算法坐儿，回溯之前沿著一個方向explore AFAP.
DFS可以用遞歸(recursive) 或者迭代的方式實現(xiàn)闰围。recursive method的general 實現(xiàn)邏輯如下：
/***
input: 圖和圖中一個節(jié)點
output: v可以達到的所有節(jié)點被labeled as discovered.
***/
void DFS(graph, v){
label v as discovered
for all directed edges from v to w in G.adjacentEdges(v)
if vertex w is not labeled as discovered:
DFS(G,w)
}
時間復(fù)雜度為O(n). 空間復(fù)雜度為調(diào)用棧的深度worst case is O(|E|)店雅。|E| 為edge的個數(shù)淹魄。
iterative 的實現(xiàn)方式如下, 空間復(fù)雜度worst-case同樣為O(|E|):
void DFS-iterative(graph, v){
let S be a stack
S.push(v)
whille(!S.isEmpty()){
v = S.pop()
label v as discovered
for all edges from v to w in G.adjacentEdges(v){
S.push(w)
}
}
}
DFS的遞歸實現(xiàn)和迭代實現(xiàn)糖荒，在現(xiàn)實生活中都有應(yīng)用，各有優(yōu)缺點围来，取決于具體應(yīng)用場景:
Recursive: 實現(xiàn)簡單刺桃，容易理解，在調(diào)用棧層數(shù)不多（Java將每層的方法調(diào)用（frame）存在方法棧當中桶蛔，而方法棧的內(nèi)存遠小于heap）的情況下匙头，可以使用。但實際生產(chǎn)中仔雷，圖大多比較龐大復(fù)雜蹂析，比如朋友圈，Google的網(wǎng)頁碟婆，交通路線圖等电抚，我們通常避免使用遞歸調(diào)用，容易產(chǎn)生StackOverflow的問題竖共。
Iterative: 使用stack數(shù)據(jù)結(jié)構(gòu)（Java會將這個棧分配在heap中）蝙叛，保存回溯路徑。相比于Recursive實現(xiàn)復(fù)雜些公给，不容易直接想到借帘。在算法面試或者競賽中，通常不會使用淌铐。
本文主要圍繞DFS肺然，來講解四道經(jīng)典的面試算法題，盡管Leetcode上有200多道DFS類相關(guān)的題型腿准，但掌握了本文的四道算法題思路际起，解決其他問題基本上沒啥問題。
Note: 不要將DFS的Iterative實現(xiàn)和BFS混淆吐葱，盡管兩者都是非遞歸調(diào)用實現(xiàn)街望，但是explore圖的方向不同，BFS講究由里到外的"地毯式搜索"弟跑，而DFS則會沿著一條路徑走到黑它匕，然后回溯。
子集合問題
題目要求print給定集合所有的subset窖认，比如given input = {1, 2, 3}豫柬，那么expected輸出應(yīng)該為{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}。
解題思路：打印出給定集合的所有子集本質(zhì)上是一道數(shù)學題扑浸，給定集合每個元素都是相互獨立的烧给，它可以出現(xiàn)或者不出現(xiàn)在子集中，那么現(xiàn)在有3個元素喝噪，最中就會有2^3 = 8 種組合础嫡。想清楚這點之后，接下來就可以考慮構(gòu)建遞歸樹酝惧，構(gòu)建遞歸樹之前呢榴鼎，我們需要問自己兩個問題：
- 遞歸樹每層代表什么含義？
Ans: 每層樹表示的含義是對于每個元素是選取還是不選取晚唇，那么遞歸樹一共有3層 - 每層有多少狀態(tài)巫财？
Ans: 每層有兩個狀態(tài)（選擇或者不選擇），那么三層樹哩陕，最終會有8個狀態(tài)平项，總體的時間復(fù)雜度為(2^n)， n為input的size悍及。
想清楚上面兩個問題就可以畫出如下的遞歸樹
圖中每個中間節(jié)點都是子集結(jié)果的臨時狀態(tài)闽瓢，而所有的葉子節(jié)點就是給定集合的子集。
OK心赶，搞定了遞歸樹的問題扣讼，代碼就很好寫了，如下所示
/**
* @param set: 給定的輸入集合[1, 2, 3]
* @param level: 當前l(fā)evel層數(shù)缨叫，表示visit 第level個元素
* @param temp:用于保存當前臨時結(jié)果集合
* @param result: 用于保存結(jié)果的集合
*/
void findSubset(int[] set, int level, List<Integer> temp, List<List<Integer>> result){
//遞歸到最后一層葉子節(jié)點
if(level == set.length){
//將臨時結(jié)果保存到最終結(jié)果集中
result.add(new ArrayList(temp));
return;
}
//選擇加入當前元素, 然后繼續(xù)向下遞歸
temp.add(set[level]);
findSubset(set, level + 1, temp, result);
//選擇不加入當前元素椭符，然后繼續(xù)向下遞歸
temp.removeLast();
findSubset(set, level + 1, temp, result);
}
相似的題型包括LC494 Target Sum, LC491 Increasing Subsequences，
硬幣組合問題
給定一組硬幣弯汰，根據(jù)已有的25, 5, 1 美分的硬幣艰山，求出所有的硬幣組合湊出給定的目標金額，比如40美分咏闪。其中每種硬幣的個數(shù)不限曙搬。這類硬幣組合問題在面試中可謂是老生常談了，比如LC518, LC322鸽嫂，LC494等等纵装。
如上題一樣，首先來畫遞歸樹据某，兩個問題
- 遞歸樹每層代表什么含義橡娄？
Ans: 每層代表使用一種類型的硬幣比如第一層只使用25美分的硬幣，有三種類型的硬幣癣籽，那么遞歸樹就有三層 - 每層有多少狀態(tài)挽唉？
Ans: 每層的狀態(tài)個數(shù)取決于當前的硬幣的類型滤祖，比如第一層目標金額為40， 選擇使用25美分的硬幣瓶籽，就有40/25 + 1 (選擇0個25沒分) = 2 種狀態(tài)匠童。遞歸樹節(jié)點最多有40狀態(tài)(選擇40 個 1 美分的硬幣，0 個25美分塑顺，0個5美分)汤求，那么時間復(fù)雜度就為O(40^3)。
接下來的就是代碼實現(xiàn)了
/***
* @param moneyLeft: 剩下錢的數(shù)量
* @param level: 當前使用的硬幣
* @param coins: 硬幣種類集合,
* @param sol: 硬幣個數(shù), sol[i]表示使用coins[i]的個數(shù)
*/
void findCombination(int moneyLeft, int level, int[] coins, int[] sol) {
If (level == coins.length - 1){
sol[level] = moneyLeft; //假設(shè)coins[3] = 1严拒，這一點要和面試官確認
print(coins, sol); //打印結(jié)果
return
}
for (int i = 0; i * coins[level] <= moneyLeft; i++){
sol[level] = i; //使用coins[level]的個數(shù)
findCombination(moneyLeft - i * coins[level] , level + 1, coins, sol );
}
}
private String print(int[] coins, int[] sol) {
for(int i = 0; i < coins.length; i++){
System.out.println("使用 {} 個 {} 美分硬幣".format(sol[i], coins[i]));
}
}
解決本題還有另外一種思路扬绪，給定三種硬幣 25, 5, 1，那么遞歸樹每一層其實有三種選擇裤唠，要么選擇1個25美分挤牛，要么選擇1個5美分，再要么選擇1個1美分巧骚，那么遞歸樹就會有99層赊颠，每層有3個選擇，時間復(fù)雜度則為O(3^99)劈彪。如果給定一個很大的目標金額竣蹦，那么很容易出現(xiàn)StackOverflow。
排列問題
Print all valid permutations of ()()()
valid case: whenever we add (, it is always valid;
Whenever we add ), we must guarantee number of the left parenthesis added so far > right parenthesis added so far.
What does it stores on each level ? (每層表什么含義)
Six levels, for each level, it makes the decision whether to put left or right parenthesis on each position.
How many different stages should we try to put on this level ? (每層有多少個狀態(tài))
兩個狀態(tài). Add Left parenthesis or right parenthesis
[圖片上傳失敗...(image-7c71eb-1573464603037)]
正在上傳...[取消](javascript:void(0))
void DFS(int left, int right, String temp, List<String> result){
if (left == n && right == n){
result.add(temp.toString());
}
if (left < n){
DFS(left + 1, right, temp + “(”, result);
}
if(right < left){
DFS(left, right + 1, temp + “)”, result);
}
}
DFS絕大部分問題的解題思路是枚舉出所有的組合沧奴，然后根據(jù)問題要求過濾出符合條件的答案痘括。
補充說明
畫遞歸樹主要幫助我們分析時間復(fù)雜度。
Print all valid permutations of ()()() 左括號滔吠，右括號
湊硬幣金額根據(jù)已有的 1, 5, 25分coin纲菌， 打印出所有的組合，99金幣
Given a String, and output all permutation ------->switch 來, switch去
Permutation of a String with (without) duplication
Permutation of all subsequences of a sorted string (allow a set contains duplicate string)
Permutation of factors of number
Levels
生成隨機的maze
重建行程單疮绷，給定一組行程列表 list of <start, end>翰舌，求訪問node的順序，如果多個path 存在冬骚，取lexical order 較小的那個
Tree的Traversal, pre-order, in-order and post-order
例題4. Given a String, and output all permutation
For example, s = “abc”
DFS基本分析法
What does it stores on each level ? (每層表什么含義)
3, each level represents each position, the character we can choose
How many different stages should we try to put on this level ? (每層有多少個狀態(tài))
第一個postion, we have 3 choice, 第二個postion, we have 2 choice, 第三個只有一個
時間復(fù)雜度取決于數(shù)最后一層節(jié)點的個數(shù)O(n!)
[圖片上傳失敗...(image-745401-1573464603037)]
正在上傳...[取消](javascript:void(0))
Both BFS and DFS can solve permutation issue, but we don’t use BFS, since BFS may have very large queue size, due to recursive tree grows exponentially. OOM
