思路：

注意每个元素可以选任意多次。

所以backtrack的时候，每次前往下一层，都是从当前层的遍历的到的位置开始进入下一层。

当pathSum == target就找到一种情况了。

当pathSum > target提前返回。

class Solution {private List<List<Integer>> res = new ArrayList<>();private List<Integer> path = new ArrayList<>();private int pathSum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {backtrack(candidates, target, 0);return res;}private void backtrack(int[] nums, int target, int startIndex) {// sum多了，结束if (pathSum > target) {return;}// 找到一种组合的情况if (pathSum == target) {res.add(new ArrayList(path));return;}// 从index开始，加入path。for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);pathSum += nums[i];// 注意！因为可以重复选，下一层是从i开始选！backtrack(nums, target, i);pathSum -= nums[i];path.remove(path.size() - 1);}}
}

思路：

一个原则：左括号要优先于右括号出现。

所以优先填n个左括号，再一个个回溯，尝试填右括号。

class Solution {private List<String> res = new ArrayList<>();private char[] path;private int n;public List<String> generateParenthesis(int n) {path = new char[n * 2];this.n = n;dfs(0, 0);return res;}// 目前填了 left 个左括号，right 个右括号private void dfs(int left, int right) {// 填完 2n 个括号if (right == n) {res.add(new String(path));return;}// 先填左括号if (left < n) {// 直接覆盖，所以不用回溯path[left + right] = '(';dfs(left + 1, right);}// 可以填右括号if (right < left) {path[left + right] = ')';dfs(left, right + 1);}}
}

思路：

• 找到一个第一个字母匹配的格子，从这里开始dfs进去搜。
• 定义 dfs(i,j,k) 表示当前在 board[i][j] 这个格子，要匹配 word[k]，返回在这个状态下最终能否匹配成功（搜索成功）。
  1. 不匹配，返回false
  2. 如果匹配完了，返回true
  3. 匹配到中间，k位置已经匹配好了，先标记board=0表示已访问。
     • 搜索格子周边的四个格子，如果没出界的话，dfs进去，探索board[x][y]和word[k+1]是不是相等。
       • 如果下面格子返回true,表示最终找到了(因为是深搜,已经搜到结尾了),直接向上返回true
  4. 如果周边四个格子都返回false，要恢复现场.把board标记还原回去，再return false

class Solution {private static final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };private char[] word;private char[][] board;public boolean exist(char[][] board, String word) {this.board = board;this.word = word.toCharArray();// 遍历board每一个格子for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == this.word[0] && dfs(i, j, 0)) {return true;}}}return false;}// 表示当前在 board[i][j] 这个格子，要匹配 word[k]private boolean dfs(int i, int j, int k) {if (board[i][j] != word[k]) {return false;}// 匹配完了，返回trueif (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 (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {continue;}// 如果下面格子返回true,表示最终找到了(因为是深搜,已经搜到结尾了),直接向上返回trueif (dfs(x, y, k + 1)) {return true;}}// 走到这里,从这里出发不能找到,return false之前,要恢复现场.把board标记还原回去board[i][j] = word[k];return false;}
}

灵茶山艾府：

还可以优化的点：

1. 统计board和word的字母出现次数，但凡word有一个字母的出现次数比board多，都不可能完成匹配，直接返回false，不用dfs了
2. 检查word的首端字母和尾端字母，谁在board的出现频次高。如果首端的出现次数明显多于尾端，那么reverse这个word，这样能减少递归次数。