課程資訊
此為Alphacamp的Leetcode訓練營課程，內文僅為個人心得。
練習題：
113. Path Sum II
題目敘述：
給予一個binary tree與一個數值targetSum，請找出root到leave的總和為targetSum，並把這路徑上的node值依序存成陣列，回傳所有可能的路徑
解法：
解法1
思路：
binary tree必須要每個node都走過才知道所有數值，所以需要一邊遍歷一邊把經過的node值貯存，同時把targetSum減去該值；題目要求root到leave，所以當node還有children node時，繼續遍歷，直到沒有children node為止，此時檢查targetSum是否為0，是的話就把目前記錄的路徑存起來
- 檢查root是否存在，沒有 → 回傳空陣列，有 → 開始遍歷
- 建立函式search，Base case為當沒有node時結束
- General Case檢查是否為leave node，是 → 檢查總和是否為所求，是的話回傳該路徑；否 → 繼續檢查左右node
解法2
698. Partition to K Equal Sum Subsets
題目敘述：
給予一個整數數字的陣列nums與一個整數k，求是否該nums能切割成k個陣列，且每個陣列總和相同。
解法：
解法1
思路：
當提供的陣列能切成k個陣列，而且每個陣列內的數字總和相同時，代表兩個條件：
1. k必定能整除陣列中的所有數字總和
2. 陣列中任一數字必定小於陣列內數字總和
- 檢查”k必定能整除陣列中的所有數字總和”、”陣列中任一數字必定小於陣列內數字總和”，如果不符合，回傳false
- 用一個名為IndexOfUsedNumbers的set紀錄使用過的數字index，一個recursion函式檢查是否為所求
- recursion函式參數為搜尋起始的index與目標總和target(陣列內數字總和)，假設nums符合要求，必定有一個組合能符合條件，每次recursion時都記錄目前的index與target，直到找到符合條件為止
- Base Case：IndexOfUsedNumbers內的數量等同於nums的長度
- General Case：
A.當target扣到小於0時，代表無法組成指定的總和，回傳false
B.當target剛好為0，代表找到符合的組合，接著找下一個組合直到符合Base Case為止
C.從index開始往後找所有數字的組合，當該數字沒有使用過時，紀錄到IndexOfUsedNumbers，接著從index+1開始找(因為符合條件時，必定有組合，不必從0開始找)，並target為陣列內數字總和扣除該數字的值；符合 → 回傳true，不符合 → 從IndexOfUsedNumbers刪除該數字的index，繼續找下一個組合
D.當所有數字都找不到時，代表沒有任何組合能符合要求，回傳false - 參考
解法2
77. Combinations
題目敘述：
給予兩個數字n與k分別代表可以使用的數字與使用的數字數量上限，求不重複數字的組合，並以陣列回傳。
例如
combine (5,2)會得到
[
[1,2],[1,3],[1,4],[1,5]
[2,3],[2,4],[2,5]
[3,4],[3,5]
[4,5]
]combine (5,3)會得到
[
[1,2,3],[1,2,4],[1,2,5],
[1,3,4],[1,3,5],
[1,4,5],
[2,3,4],[2,3,5],[2,4,5],
[3,4,5]
]解法：
解法1
思路：
以上面的例子可以看到一些規則：
1. 所有排列中，有些組合會有相同數字，只有最後的數字不同
2.如果陣列第一個數字是N，則後面出現的數字不會小於N
→需要紀錄前面的組合，把接下來會出現的數字依序下去排列
pseudocode：
1. 用一個陣列result貯存結果
2. 以DFS方式遞迴製造組合，直到陣列中產生ｋ個數字
3. 回傳結果
以combine (5,3)為例子
一開始會產生陣列[1]，以這個陣列為基礎繼續疊加其他數字：
[1,2]
[1,3]
[1,4]
[1,5]接著進入[1,2]，繼續疊加後面的數字
[1,2,3]
[1,2,4]
[1,2,5]由於陣列已經有三個數字，達到要求，所以記錄到Result當中
解法2