每日两题 / 79. 单词搜索 39. 组合总和（LeetCode热题100）

本文主要是介绍每日两题 / 79. 单词搜索 39. 组合总和（LeetCode热题100），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

遍历board，遇到字符等于word的第一个字符时，进行dfs回溯
设置访问数组，标记已经走过的坐标
每次dfs时，往四个方向走，若当前字符不匹配则回溯，记得消除访问数组对应的标记

class Solution {
public:int n, m, l;bool st[10][10];int dx[4] = { 0, 0, 1, -1 }, dy[4] = { 1, -1, 0, 0 };bool dfs(vector<vector<char>>& board, string& word, int x, int y, int i) {if (word[i] != board[x][y]) return false;st[x][y] = true;if (i + 1 == l) return true;bool res = false;for (int j = 0; j < 4; ++ j) {int nx = x + dx[j], ny = y + dy[j];if (nx < n && nx >= 0 && ny < m && ny >= 0 && !st[nx][ny])res |= dfs(board, word, nx, ny, i + 1);if (res) return true;}st[x][y] = false;return false;}bool exist(vector<vector<char>>& board, string word) {l = word.size(), n = board.size(), m = board[0].size();for (int i = 0; i < n; ++ i)for (int j = 0; j < m; ++ j)if (board[i][j] == word[0]) {memset(st, 0, sizeof st);if (dfs(board, word, i, j, 0))return true;}return false;}
};

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

每次的dfs在[bg, end]中，从左往右选择一个数，并更新bg为这个数所在的下标
若bg总是为0，将出现重复的组合

class Solution {
public:vector<vector<int>> ans;void dfs(vector<int>& candidates, int target, int cur, vector<int> &t, int bg) {if (cur == target) ans.push_back(t);else if (cur > target) return;for (int i = bg; i < candidates.size(); ++ i) {int num = candidates[i];t.push_back(num);dfs(candidates, target, cur + num, t, i);t.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> t;dfs(candidates, target, 0, t, 0);return ans;}
};