1.39. 组合总和 - 力扣（LeetCode）

对于这类寻找所有可行解的问题，都可以尝试使用 [搜索回溯] 的方法。以下是朴素不减脂的方法，我昨天吃了个干煸炒面，巨朴素。。。一点都不减脂，但是很好吃~~~

class Solution {
private:void dfs(vector<int> &candidates, vector<vector<int>> &ans, int target, vector<int> combine, int idx) {if(idx == candidates.size()) return;if(target == 0){ans.emplace_back(combine);return;}          dfs(candidates, ans, target, combine, idx+1);// 等于0的情况是当下的元素也满足条件构造一个答案if(target - candidates[idx] >= 0){combine.emplace_back(candidates[idx]);// 元素可以重复使用所以不用idx+1dfs(candidates, ans, target - candidates[idx], combine, idx);combine.emplace_back();}}    
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> combine;vector<vector<int>> ans;dfs(candidates, ans, target, combine, 0);return ans;}
};

第一个return 是当索引超出候选范围时停止，避免无效的递归。第二个return 是已经找到一个结果，该分支下没有再找的必要。combine.pop_back(); 是重要的一步，回溯的核心思想就在这里了，它帮助我们撤销选择，是算法尝试其他的组合。

2.70. 爬楼梯 - 力扣（LeetCode）

 玛雅 这有好多种方法，用最简单的递归会超时。

class Solution {
public:int climbStairs(int n) {// p：从第i-2阶走两步的方法的数量// q：从第i-1阶走一步这种方法的数量// r；走到第i阶的方法总数int p = 0, q = 0, r = 1;for(int i = 1; i <= n; i++) {p = q; // 计算这一轮到达i-2的方法数量 等于 上一轮从i-1走一步的方法数量q = r; // 计算这一轮到达i-1的方法数量 等于 到达上一轮i的方法数量r = p + q;}/*初始化状态在地面，即走到0阶梯，只有1种方法，原地不动。当要走到阶梯1时，从-1阶梯开始走两步有0种走法，从0阶梯开始走一步有1种走法 共1种当要走到阶梯2时，从0阶梯开始走两步有1种走法，从1阶梯开始走一步有1种走法 共2种当要走到阶梯3时，从1阶梯开始走两步有2种走法，从2阶梯开始走一步有1种走法 共3种*/return r;}
};

3.79. 单词搜索 - 力扣（LeetCode）

class Solution {
public:int rows,cols;bool exist(vector<vector<char>>& board, string word) {rows = board.size();cols = board[0].size();for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {if(dfs(board, word, i, j, 0)) return true;}}return false;}
private:bool dfs(vector<vector<char>>& board, string word, int i, int j, int idx) {if(i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != word[idx])return false;if(idx == word.size() - 1) return true;board[i][j] = '\0';bool res = dfs(board, word, i, j-1, idx+1) || dfs(board, word, i-1, j, idx+1) ||dfs(board, word, i, j+1, idx+1) || dfs(board, word, i+1, j, idx+1);board[i][j] = word[idx];return res;}
};

其实我觉得这是一道中规中矩的递归搜索题。。。