hot100 -- 回溯（上）

目录

科普

全排列

AC  DFS

子集

AC  DFS

电话号码的字母组合

AC  DFS

组合总和

AC  DFS

---

科普

忘记 dfs 的，先看看这个

DFS（深度优先搜索）8种题型_dfs典型问题-CSDN博客

全排列

46. 全排列 - 力扣（LeetCode）

AC  DFS

排列型枚举哦~

坑

vectindex.php/tags-1038.html" >or 中 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 ans;    vector ret; // 临时答案    bool vis[7]; // 标记数组--需要回溯    void dfs(vector& nums, int count) {        int n = nums.size();        // 递归出口        if (count == n) {            ans.push_back(ret);            return;        }                // 遍历每个位置        for (int i = 0; i  
子集
 
78. 子集 - 力扣（LeetCode）
 
指数型枚举哦~
 
AC  DFS
   
只有 选 / 不选 两种
  
时间 O(n * 2^n)，空间 O(n)
 
class Solution {private:    vector ans;    vector ret; // 临时答案public:    void dfs(vector& 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 subsets(vector& 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 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  
组合总和
 
39. 组合总和 - 力扣（LeetCode）
 
AC  DFS
   
1）指数型枚举的前提下，一个数字可以 “无限制重复” 被选取
    
2）还要考虑到，这题是 组合 问题，相同组合不同排列，视为同一种结果
    
3）分两种情况讨论，选 / 不选，注意参数的不同
  
class Solution {private:    vector ans;    vector ret; // 临时答案    // num - candidates[i], num == 0 得到一个结果    // 剩余 num, 第 start 个数字    void dfs(vector& candidates, int num, int start) {        int n = candidates.size();        // 递归出口        if (start >= n) return;        // 一种结果        if (num == 0) {            ans.push_back(ret);            return;        }        // 选（当前数字）        // 不超过 target        if (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 combinationSum(vector& candidates, int target) {    dfs(candidates, target, 0); // 剩余 target, 第 0 个数字开始    return ans;    }};