LeetCode 热题 100 之 39. 组合总和 22. 括号生成 79. 单词搜索

39.组合总和22.括号生成79.单词搜索39. 组合总和class Solution { public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); backtrack(candidates, target, 0, 0, path, res); return res; } /** * param candidates 候选数组 * param target 目标和 * param start 遍历起点避免重复组合 * param sum 当前路径和 * param path 当前组合路径 * param res 结果集合 */ private void backtrack(int[] candidates, int target, int start, int sum, ListInteger path, ListListInteger res) { // 终止条件和等于目标加入结果 if (sum target) { res.add(new ArrayList(path)); return; } // 剪枝和超过目标直接返回 if (sum target) { return; } // 从 start 开始遍历保证组合不重复 for (int i start; i candidates.length; i) { path.add(candidates[i]); // 递归可重复选当前元素故 start 仍为 i backtrack(candidates, target, i, sum candidates[i], path, res); // 回溯撤销选择 path.remove(path.size() - 1); } } }解题思路回溯法路径与选择用path记录当前组合遍历candidates时每次可以选择继续选当前元素因为可重复或跳过当前元素避免重复组合。剪枝优化若当前路径和已超过target直接终止该分支若等于target则将路径加入结果集。避免重复通过控制遍历起点从当前索引开始保证组合内元素按顺序选取不会出现[2,3]和[3,2]这类重复结果。22. 括号生成class Solution { public ListString generateParenthesis(int n) { ListString res new ArrayList(); backtrack(n, 0, 0, new StringBuilder(), res); return res; } /** * param n 目标括号对数 * param open 当前左括号数量 * param close 当前右括号数量 * param path 当前拼接的括号字符串 * param res 结果集合 */ private void backtrack(int n, int open, int close, StringBuilder path, ListString res) { // 终止条件左右括号数量都等于 n形成有效组合 if (open n close n) { res.add(path.toString()); return; } // 约束1左括号未达上限可添加 ( if (open n) { path.append((); backtrack(n, open 1, close, path, res); path.deleteCharAt(path.length() - 1); // 回溯 } // 约束2右括号数量小于左括号可添加 ) if (close open) { path.append()); backtrack(n, open, close 1, path, res); path.deleteCharAt(path.length() - 1); // 回溯 } } }解题思路回溯法这是典型的带约束的回溯问题核心是通过两个计数器控制括号合法性open已使用的左括号数量close已使用的右括号数量约束规则左括号最多可以加n个当open n时可以添加(右括号只能在close open时添加保证任意前缀中左括号数量 ≥ 右括号数量当open close n时得到一个完整有效组合79. 单词搜索class Solution { public boolean exist(char[][] board, String word) { int m board.length; int n board[0].length; // 遍历每个单元格作为起点 for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] word.charAt(0)) { if (dfs(board, word, i, j, 0)) { return true; } } } } return false; } /** * param board 字符网格 * param word 目标单词 * param i 当前行坐标 * param j 当前列坐标 * param k 当前匹配到单词的第 k 位 * return 是否能从 (i,j) 出发匹配完 word */ private boolean dfs(char[][] board, String word, int i, int j, int k) { // 终止条件已匹配完所有字符 if (k word.length()) { return true; } // 边界判断 字符不匹配 int m board.length; int n board[0].length; if (i 0 || i m || j 0 || j n || board[i][j] ! word.charAt(k)) { return false; } // 标记当前单元格为已访问避免重复使用 char temp board[i][j]; board[i][j] #; // 向四个方向递归搜索 boolean found dfs(board, word, i 1, j, k 1) || dfs(board, word, i - 1, j, k 1) || dfs(board, word, i, j 1, k 1) || dfs(board, word, i, j - 1, k 1); // 回溯恢复单元格原值 board[i][j] temp; return found; } }解题思路回溯 DFS遍历起点先遍历网格中所有与word首字母相同的单元格作为搜索起点。深度优先搜索DFS从起点出发向上下左右四个方向探索匹配word的下一个字符。回溯与标记用原网格标记已访问的单元格临时修改字符避免重复访问递归结束后恢复原值回溯。剪枝若当前字符不匹配直接终止该分支若已匹配完整个单词返回true。灵茶山艾府解法class Solution { private static final int[][] DIRS {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; public boolean exist(char[][] board, String word) { char[] w word.toCharArray(); for (int i 0; i board.length; i) { for (int j 0; j board[i].length; j) { if (dfs(i, j, 0, board, w)) { return true; // 搜到了 } } } return false; // 没搜到 } private boolean dfs(int i, int j, int k, char[][] board, char[] word) { if (board[i][j] ! word[k]) { // 匹配失败 return false; } if (k word.length - 1) { // 匹配成功 return true; } board[i][j] 0; // 标记访问过 for (int[] d : DIRS) { int x i d[0]; int y j d[1]; // 相邻格子 if (0 x x board.length 0 y y board[x].length dfs(x, y, k 1, board, word)) { return true; // 搜到了 } } board[i][j] word[k]; // 恢复现场 return false; // 没搜到 } } 作者灵茶山艾府 链接https://leetcode.cn/problems/word-search/solutions/2927294/liang-ge-you-hua-rang-dai-ma-ji-bai-jie-g3mmm/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。class Solution { private static final int[][] DIRS {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; public boolean exist(char[][] board, String word) { // 为了方便直接用数组代替哈希表 int[] cnt new int[128]; for (char[] row : board) { for (char c : row) { cnt[c]; } } // 优化一 char[] w word.toCharArray(); int[] wordCnt new int[128]; for (char c : w) { if (wordCnt[c] cnt[c]) { return false; } } // 优化二 if (cnt[w[w.length - 1]] cnt[w[0]]) { w new StringBuilder(word).reverse().toString().toCharArray(); } for (int i 0; i board.length; i) { for (int j 0; j board[i].length; j) { if (dfs(i, j, 0, board, w)) { return true; // 搜到了 } } } return false; // 没搜到 } private boolean dfs(int i, int j, int k, char[][] board, char[] word) { if (board[i][j] ! word[k]) { // 匹配失败 return false; } if (k word.length - 1) { // 匹配成功 return true; } board[i][j] 0; // 标记访问过 for (int[] d : DIRS) { int x i d[0]; int y j d[1]; // 相邻格子 if (0 x x board.length 0 y y board[x].length dfs(x, y, k 1, board, word)) { return true; // 搜到了 } } board[i][j] word[k]; // 恢复现场 return false; // 没搜到 } } 作者灵茶山艾府 链接https://leetcode.cn/problems/word-search/solutions/2927294/liang-ge-you-hua-rang-dai-ma-ji-bai-jie-g3mmm/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。总结这三道题均以回溯算法为核心组合总和通过控制遍历起点避免重复组合并剪枝括号生成利用左右括号数量约束保证合法性单词搜索采用 DFS 四向查找并标记回溯灵茶山艾府版还通过字符计数与反转单词进一步优化效率整体均遵循 “选择 — 递归 — 撤销选择” 的回溯核心思想。