40. Combination Sum II
題目網址：https://leetcode.cn/problems/combination-sum-ii/
題意：給一 array candidates 和一整數 target, 求 candidates 中所有可以使數字和為 target 的組合, 且 candidates 中的每個數字在每個組合中只能使用一次。
注意：Output 不能有重複的組合
Solution 1：
想法：先做 sorting, 再用 DFS, 類似 39. Combination Sum, 一旦不取 nums[j], 則後面區間 [j + 1, n) 中若有跟 candidates[j] 相同的都直接跳過
e.g. candidates = [10,1,2,7,6,1,5], target = 8
先做 sorting
若不取 idx = 0 的 1, 則可以直接跳過 idx = 1 的 1, 讓 idx = 2 的元素開始取
class Solution {public: vector<vector<int>> combinationSum2(vect ...
79. Word Search
題目網址：https://leetcode.cn/problems/word-search/
題意：給一 m x n 的網格 board 和一 string word, 求 word 是否出現在 board 中。
其中, board 和 word 僅由大小寫英文字母所組成
注意：必須按照 word 中字母的順序, 並通過相鄰的 cell 所構成, 其中相鄰是指水平相鄰 or 垂直相鄰, 且同一位置的 cell 不允許被重複使用。
Solution：
想法：利用 DFS, 要記得將已拜訪過的 node 設為已拜訪, 避免重複拜訪
class Solution {public: bool exist(vector<vector<char>>& board, string word) { m = board.size(), n = board[0].size(); // 依序把 board[i][j] 作為起始點來探索 for (int i = 0; i < m; ++i) ...
131. Palindrome Partitioning
題目網址：https://leetcode.cn/problems/palindrome-partitioning/
題意：給一 string s, 將 s 切割成一些 substring, 使每個 substring 皆回文, 返回 s 所有可能的切割方法。
其中, s 僅由小寫英文字母所組成。
Solution：
想法：利用 DFS, 如果切下去是回文, 則遞迴剩下的 substring
class Solution {public: vector<vector<string>> partition(string s) { dfs(s, 0, s.size()); return res; }private: vector<string> cur; vector<vector<string>> res; void dfs(const string& s, const int i, const int n){ ...
17. Letter Combinations of a Phone Number
題目網址：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
題意：給一 string 包含數字 2-9, 以任意順序返回所有它所能表示的英文組合。數字到英文的 mapping 如下, 其中數字 1 不對應任何字母
Solution：
想法：利用 DFS + Backtracking
class Solution {public: vector<string> letterCombinations(string digits) { if (digits.size() == 0) { return {}; } dfs(digits, 0, digits.size()); return res; }private: string cur; vector<string> res; vector< ...
200. Number of Islands
題目網址：https://leetcode.cn/problems/number-of-islands/
題意：給一 m x n 的二維矩陣 grid, 其中 '1' 代表陸地, 而 '0' 代表水, 返回島嶼的個數。
每座島嶼只能由水平 or 垂直方向的相鄰陸地連接而成。
Solution 1：
想法：利用 DFS, 若 grid[row][col] == 1, 則以其為起始 node 開始進行 DFS。在 DFS 的過程中. 每個搜索到的 1 都會被重新標記為 0, 最後整個地圖都會變成水
class Solution {public: int numIslands(vector<vector<char>>& grid) { m = grid.size(), n = grid[0].size(); int res = 0; for (int i = 0; i < m; ++i) { for (int j ...