> HOT 回溯章节，这个部分基本就是默写了，推荐去看b站的灵神的算法精讲视频，我很多思路或者题解都是从那里学会的。睡觉，今天就到这了....祝好梦 1. [78. 子集 - 力扣（LeetCode）](https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked) 2. [46. 全排列 - 力扣（LeetCode）](https://leetcode.cn/problems/permutations/description/?envType=study-plan-v2&envId=top-100-liked) 3. [17. 电话号码的字母组合 - 力扣（LeetCode）](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/?envType=study-plan-v2&envId=top-100-liked) 4. [39. 组合总和 - 力扣（LeetCode）](https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked) 5. [22. 括号生成 - 力扣（LeetCode）](https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-100-liked) 6. [79. 单词搜索 - 力扣（LeetCode）](https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked) 7. [131. 分割回文串 - 力扣（LeetCode）](https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked) 8. [51. N 皇后 - 力扣（LeetCode）](https://leetcode.cn/problems/n-queens/?envType=study-plan-v2&envId=top-100-liked) ## 子集板子题 ```java class Solution { private List> ans = new ArrayList<>(); private List path = new ArrayList<>(); private int n; private int[] nums; public List> subsets(int[] nums) { this.nums = nums; this.n = nums.length; dfs(0); return ans; } private void dfs(int i ){ ans.add(new ArrayList<>(path)); for (int j = i ; j < n; j++){ path.add(nums[j]); dfs(j + 1); path.remove(path.size()-1); } } } ``` ## 全排列板子题 ```java class Solution { private int n; private int[] nums; private boolean[] onPath; private List path = new ArrayList<>(); private List> ans = new ArrayList<>(); public List> permute(int[] nums) { int n = nums.length; this.n = n; this.nums = nums; this.onPath = new boolean[n]; dfs(0); return ans; } private void dfs(int i){ if (i == n){ ans.add(new ArrayList<>(path)); return; } for (int j = 0; j < n ; j++){ if (!onPath[j]){ path.add(nums[j]); onPath[j] = true; dfs(i + 1); path.remove(path.size()-1); onPath[j] = false; } } } } ``` ## 电话号码字母组合组合变形题 ```java class Solution { private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; private List ans = new ArrayList<>(); private char[] digits; private char[] path; private int n; public List letterCombinations(String digits) { this.digits = digits.toCharArray(); this.n = digits.length(); this.path = new char[n]; if (n == 0){ return List.of(); } dfs(0); return ans; } private void dfs(int i ){ if (i == n){ ans.add(new String(path)); return; } for (char c : MAPPING[digits[i] - '0'].toCharArray()){ path[i] = c; dfs(i + 1); } } } ``` ## 组合总和有点像二叉树路径和 ```java class Solution { private List> ans = new ArrayList<>(); private int[] candidates; private int n; private List path = new ArrayList<>(); public List> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); this.n = candidates.length; this.candidates = candidates; dfs(0,target); return ans; } private void dfs(int i , int target){ if (target == 0){ ans.add(new ArrayList<>(path)); return; } if (i == n || target < candidates[i]){ return; } dfs(i + 1, target); path.add(candidates[i]); dfs(i , target - candidates[i]); path.remove(path.size()-1); } } ``` ## 括号生成选或不选的思路推荐去看灵神的这部分的算法精讲 ```java class Solution { private int n ; private List ans = new ArrayList<>(); private char[] path; public List generateParenthesis(int n) { this.n = n; path = new char[n * 2]; dfs(0 ,0); return ans; } private void dfs(int i , int open){ if (i == n * 2){ ans.add(new String(path)); return; } if (open < n){ path[i] = '('; dfs(i + 1,open + 1); } if (i - open < open){ path[i] = ')'; dfs(i + 1,open); } } } ``` ## 单词搜索经典广度优先算法 ```java class Solution { private static final int[][] DIRS = {{0,-1},{0,1},{-1,0},{1,0}}; private char[][] board; private char[] word; public boolean exist(char[][] board, String word) { this.board = board; this.word = word.toCharArray(); for (int i = 0 ; i < board.length; i++){ for (int j = 0; j < board[i].length; j ++){ if (dfs(i , j ,0)){ return true; } } } return false; } private boolean dfs(int i , int j , int k){ 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 && board[x][y] != 0 && dfs(x, y, k +1)){ return true; } } board[i][j] = word[k]; return false; } } ``` ## 分割回文串使用选或者不选的思路，也可以直接回溯模板 ```java class Solution { private List> ans = new ArrayList<>(); private List path = new ArrayList<>(); private String s; private int n; public List> partition(String s) { this.s = s; this.n = s.length(); dfs(0,0); return ans; } private void dfs(int i , int start){ if (i == n){ ans.add(new ArrayList<>(path)); return ; } if (i < n - 1){ dfs(i + 1, start); } if (check(start , i)){ path.add(s.substring(start,i + 1)); dfs(i + 1, i + 1); path.remove(path.size()-1); } } private boolean check(int l , int r){ while (l < r){ if (s.charAt(l ++) != s.charAt(r --)){ return false; } } return true; } } ``` ## N皇后经典排列了，默写 ```java class Solution { private char[][] queens; private boolean[] onPath; private boolean[] dig1; private boolean[] dig2; private int n; private List> ans = new ArrayList<>(); public List> solveNQueens(int n) { this.n = n; this.queens = new char[n][n]; for (int i = 0 ; i < n; i++){ for (int j =0; j < n; j++){ queens[i][j] = '.'; } } this.onPath = new boolean[n]; this.dig1 = new boolean[n * 2]; this.dig2 = new boolean[n *2]; dfs(0); return ans; } private void dfs(int i){ if (i == n){ List temp = new ArrayList<>(); for (int j =0 ; j < n; j++){ temp.add(new String(queens[j])); } ans.add(temp); } for (int j = 0; j < n; j++){ if (!onPath[j] && !dig1[i + j] && !dig2[i - j + n -1]){ queens[i][j] = 'Q'; onPath[j] = dig1[i + j] = dig2[i- j + n - 1] = true; dfs(i + 1); queens[i][j] = '.'; onPath[j] = dig1[i + j] = dig2[i- j + n - 1] = false; } } } } ```

力扣刷题Hot100的全部评论