思路：

注意每個元素可以選任意多次。

所以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，這樣能減少遞歸次數。