目錄

🍞科普

🌼全排列

AC? DFS

🚩子集

AC? DFS

🎂電話號碼的字母組合

AC? DFS

🌼組合總和

AC? DFS

---

🍞科普

忘記 dfs 的，先看看這個👇

DFS（深度優先搜索）8種題型_dfs典型問題-CSDN博客

🌼全排列

46. 全排列 - 力扣（LeetCode）

AC? DFS

排列型枚舉哦~

坑

vector 中 push_back 和 [] 下標訪問是不一樣的

push_back() 是往末尾加入元素，vector 大小會自動增加

而 [] 是直接改變 vector 某個位置的元素

如果你先 ret[i] = count[i]; 然后 ret.pop_back(); 多次循環后，vector 為空，此時再訪問就會報錯空指針 Null Pointer 錯誤

時間 O(n * !n)，空間 O(n)

class Solution {
private:vector<vector<int>> ans;vector<int> ret; // 臨時答案bool vis[7]; // 標記數組--需要回溯void dfs(vector<int>& nums, int count) {int n = nums.size();// 遞歸出口if (count == n) {ans.push_back(ret);return;}// 遍歷每個位置for (int i = 0; i < n; ++i) {if (vis[i] == 0) {ret.push_back(nums[i]); // 加入答案數組vis[i] = 1; // 標記dfs(nums, count + 1); // 遞歸vis[i] = 0; // 取消標記ret.pop_back(); // 取消標記}}}public:vector<vector<int>> permute(vector<int>& nums) {\dfs(nums, 0);return ans;}};

🚩子集

78. 子集 - 力扣（LeetCode）

指數型枚舉哦~

AC? DFS

只有 選 / 不選 兩種

時間 O(n * 2^n)，空間 O(n)

class Solution {
private:vector<vector<int>> ans;vector<int> ret; // 臨時答案
public:void dfs(vector<int>& nums, int count) {int n = nums.size();// 遞歸出口if (count == n) {ans.push_back(ret);return;}// 選 OR 不選// 選ret.push_back(nums[count]); // 類似標記dfs(nums, count + 1); // 遞歸ret.pop_back(); // 類似取消標記// 不選dfs(nums, count + 1);}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ans;}
};

🎂電話號碼的字母組合

17. 電話號碼的字母組合 - 力扣（LeetCode）

AC? DFS

空數組是 {}，而不是 []，編譯器看不懂這種 lambda 表達式

本題不要標記，因為，比如 "222"，是可以取 "aaa" 的?

3 個字母的數字輸入?m 個，4 個字母的輸入?n 個

時間 O(3^m * 4^n) -- 遍歷每一種字母組合

/*
1)  n 個數字, 每個數字取 1 個字母, 共取出 n 個字母
2) 取出的 n 個字母，按順序組合起來 -- O(1)
*/
class Solution {
private:string ret; // 臨時答案vector<string> ans;string num_alpha[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};// 已選 count 個數字void dfs(string digits, int count) {int n = digits.size();if (count == n) {ans.push_back(ret);return;}int num = digits[count] - '0'; // 當前數字string now = num_alpha[num]; // 當前字符串// 取一個字母for (int i = 0; i < now.size(); ++i) {ret.push_back(now[i]); // 插入字母dfs(digits, count + 1); // 遞歸ret.pop_back(); // 回溯時，便于填充其他字母}}public:vector<string> letterCombinations(string digits) {// 特判空字符串, 返回空數組, 而不是包含空字符串的數組 [""]if (digits == "")return {};dfs(digits, 0);return ans;}
};

🌼組合總和

39. 組合總和 - 力扣（LeetCode）

AC? DFS

1）指數型枚舉的前提下，一個數字可以 “無限制重復” 被選取

2）還要考慮到，這題是 組合 問題，相同組合不同排列，視為同一種結果

3）分兩種情況討論，選 / 不選，注意參數的不同

class Solution {
private:vector<vector<int>> ans;vector<int> ret; // 臨時答案// num - candidates[i], num == 0 得到一個結果// 剩余 num, 第 start 個數字void dfs(vector<int>& candidates, int num, int start) {int n = candidates.size();// 遞歸出口if (start >= n) return;// 一種結果if (num == 0) {ans.push_back(ret);return;}// 選（當前數字）// 不超過 targetif (num - candidates[start] >= 0) {ret.push_back(candidates[start]);dfs(candidates, num - candidates[start], start); // 選當前數字ret.pop_back(); // 恢復現場}// 不選（當前數字）dfs(candidates, num, start + 1); // 遞歸下一個}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates, target, 0); // 剩余 target, 第 0 個數字開始return ans;}
};