46.全排列
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
输入：nums = [0,1]
输出：[[0,1],[1,0]]
输入：nums = [1]
输出：[[1]]
class Solution {
List<List<Integer>> res = new ArrayList<>(); // 存储结果的列表
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length]; // 记录每个元素是否已经使用过
List<Integer> track = new ArrayList<>(); // 存储当前排列的元素
backtrack(track, nums, used); // 回溯算法求解全排列
return res; // 返回结果列表
}
private void backtrack(List<Integer> track, int[] nums, boolean[] used){
if(track.size() == nums.length){ // 如果当前排列的长度等于数组长度，说明已经找到一个全排列
res.add(new ArrayList(track)); // 将当前排列添加到结果列表中
return;
}
for(int i=0 ; i<nums.length ; i++){ // 遍历数组中的每个元素
if(used[i]){ // 如果当前元素已经使用过，跳过
continue;
}
used[i] = true; // 标记当前元素为已使用
track.add(nums[i]); // 将当前元素添加到当前排列中
backtrack(track, nums, used); // 继续寻找下一个元素
used[i] = false; // 回溯，将当前元素标记为未使用
track.removeLast(); // 回溯，移除当前排列中的最后一个元素
}
}
}
78.子集
给你一个整数数组 nums ，数组中的元素互不相同 。返回该数组所有可能的
子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
输入：nums = [0]
输出：[[],[0]]
class Solution {
List<Integer> t = new ArrayList<Integer>(); // 用于存储当前子集的元素
List<List<Integer>> ans = new ArrayList<>(); // 用于存储所有子集的结果
public List<List<Integer>> subsets(int[] nums) {
dfs(0, nums); // 从第0个元素开始进行深度优先搜索
return ans; // 返回所有子集的结果
}
public void dfs(int cur, int[] nums) {
if (cur == nums.length) { // 如果已经遍历完所有元素，将当前子集添加到结果中
ans.add(new ArrayList<Integer>(t));
return;
}
t.add(nums[cur]); // 将当前元素添加到子集中
dfs(cur + 1, nums); // 继续向下搜索
t.remove(t.size() - 1); // 回溯，移除刚刚添加的元素
dfs(cur + 1, nums); // 不包含当前元素的子集继续向下搜索
}
}
还有一种题解很有意思
- 例如[1,2,3]，一开始解集为[[]]，表示只有一个空集。
- 遍历到1时，依次拷贝解集中所有子集，只有[]，把1加入拷贝的子集中得到[1]，然后加回解集中。此时解集为[[], [1]]。
- 遍历到2时，依次拷贝解集中所有子集，有[], [1]，把2加入拷贝的子集得到[2], [1, 2]，然后加回解集中。此时解集为[[], [1], [2], [1, 2]]。
- 遍历到3时，依次拷贝解集中所有子集，有[], [1], [2], [1, 2]，把3加入拷贝的子集得到[3], [1, 3], [2, 3], [1, 2, 3]，然后加回解集中。此时解集为[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> lists = new ArrayList<>(); // 解集
lists.add(new ArrayList<Integer>()); // 首先将空集加入解集中
for(int i = 0; i < nums.length; i++){
int size = lists.size(); // 当前子集数
for(int j = 0; j < size; j++){
List<Integer> newList = new ArrayList<>(lists.get(j));// 拷贝所有子集
newList.add(nums[i]); // 向拷贝的子集中加入当前数形成新的子集
lists.add(newList); // 向lists中加入新子集
}
}
return lists;
}
}
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入：digits = ""
输出：[]
输入：digits = "2"
输出：["a","b","c"]
class Solution {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<String>(); // 存储所有可能的组合结果
if(digits.length() == 0){ // 如果输入为空，直接返回空列表
return combinations;
}
Map<Character,String> phoneMap = new HashMap<Character,String>(){{ // 创建一个映射表，将数字映射到对应的字母
put('2',"abc");
put('3',"def");
put('4',"ghi");
put('5',"jkl");
put('6',"mno");
put('7',"pqrs");
put('8',"tuv");
put('9',"wxyz");
}};
backtracking(combinations,phoneMap,digits,0,new StringBuffer()); // 调用回溯函数进行搜索
return combinations; // 返回所有可能的组合结果
}
public void backtracking(List<String> combinations,Map<Character,String> phoneMap,String digits,int index,StringBuffer combination){
if(index == digits.length()){ // 如果已经遍历完所有的数字，将当前组合添加到结果列表中
combinations.add(combination.toString());
}else{
char digit = digits.charAt(index); // 获取当前数字
String letters = phoneMap.get(digit); // 获取当前数字对应的字母
int lettersCount = letters.length(); // 获取当前数字对应的字母数量
for(int i=0;i<lettersCount;i++){ // 遍历当前数字对应的所有字母
combination.append(letters.charAt(i)); // 将当前字母添加到组合中
backtracking(combinations,phoneMap,digits,index+1,combination); // 继续搜索下一个数字
combination.deleteCharAt(index); // 回溯，移除刚刚添加的字母
}
}
}
}
39.组数总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
输入: candidates = [2], target = 1
输出: []
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 存储结果的列表
List<Integer> combine = new ArrayList<Integer>(); // 存储当前组合的列表
dfs(candidates, target, ans, combine, 0); // 调用深度优先搜索函数
return ans; // 返回结果列表
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) { // 如果已经遍历完所有候选数，直接返回
return;
}
if (target == 0) { // 如果目标值减为0，说明找到了一个有效的组合，将其添加到结果列表中
ans.add(new ArrayList<Integer>(combine));
return;
}
dfs(candidates, target, ans, combine, idx + 1); // 不选择当前候选数，继续搜索下一个候选数
if (target - candidates[idx] >= 0) { // 如果选择当前候选数后，目标值仍然大于等于0，继续搜索
combine.add(candidates[idx]); // 将当前候选数添加到当前组合中
dfs(candidates, target - candidates[idx], ans, combine, idx); // 继续搜索剩余的目标值
combine.remove(combine.size() - 1); // 回溯，移除刚刚添加的候选数
}
}
}
79.单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
class Solution {
public boolean exist(char[][] board, String word) {
int h = board.length, w = board[0].length;
boolean[][] visited = new boolean[h][w];
// 遍历二维数组的每个元素
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
// 检查当前位置是否能够匹配单词的前缀
boolean flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
// 如果当前位置的字符与单词的第k个字符不匹配，返回false
if (board[i][j] != s.charAt(k)) {
return false;
} else if (k == s.length() - 1) {
// 如果已经匹配到单词的最后一个字符，返回true
return true;
}
// 标记当前位置已访问
visited[i][j] = true;
// 定义四个方向的偏移量
int[][] directions = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
boolean result = false;
// 遍历四个方向
for (int[] dir : directions) {
int newi = i + dir[0], newj = j + dir[1];
// 判断新的位置是否在二维数组范围内
if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
if (!visited[newi][newj]) {
// 递归调用check函数，继续匹配下一个字符
boolean flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
// 回溯，将当前位置标记为未访问
visited[i][j] = false;
return result;
}
}
- 将输入的字符串word转换为字符数组words。
- 遍历二维数组board的每一个元素，对于每一个元素，调用dfs函数进行深度优先搜索。
- 在dfs函数中，首先判断当前位置是否越界或者当前位置的字符与word中的对应字符不相等，如果满足这些条件，则返回false。
- 如果已经匹配到word的最后一个字符，说明找到了一个有效的路径，返回true。
- 将当前位置的字符暂时替换为’\0’，避免重复访问。
- 递归地对当前位置的上下左右四个方向进行深度优先搜索，如果有一个方向返回true，说明找到了一个有效的路径，返回true。
- 恢复当前位置的字符，继续搜索其他可能的路径。
- 如果所有方向都没有找到有效的路径，返回false。
- 如果遍历完二维数组board的所有元素都没有找到有效的路径，返回false。
class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if (dfs(board, words, i, j, 0)) return true;
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
if (k == word.length - 1) return true;
board[i][j] = '\0';
boolean res = 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] = word[k];
return res;
}
}
131.分割回文子串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
输入：s = "a"
输出：[["a"]]
class Solution {
List<String> path = new ArrayList<>(); // 存储回文子串的路径
List<List<String>> result = new ArrayList<>(); // 存储所有可能的回文子串组合
public List<List<String>> partition(String s) {
backtracking(s, 0); // 从字符串的第一个字符开始进行回溯
return result; // 返回所有可能的回文子串组合
}
void backtracking(String s, int startIndex) {
if (startIndex == s.length()) { // 如果已经遍历到字符串的末尾
result.add(new ArrayList<>(path)); // 将当前路径添加到结果中
return;
}
for (int i = startIndex + 1; i <= s.length(); i++) { // 遍历字符串，找到所有可能的回文子串
String substring = s.substring(startIndex, i); // 获取当前子串
if (!isPalindrome(substring)) { // 如果当前子串不是回文，跳过
continue;
}
path.add(substring); // 将当前回文子串添加到路径中
backtracking(s, i); // 继续向后遍历
path.remove(path.size() - 1); // 回溯，移除当前回文子串
}
}
boolean isPalindrome(String s) { // 判断一个字符串是否是回文
int left = 0;
int right = s.length() - 1;
while (left < right) { // 从两端向中间遍历
if (s.charAt(left) != s.charAt(right)) { // 如果两端的字符不相等，说明不是回文
return false;
}
left++;
right--;
}
return true; // 如果遍历完没有发现不相等的字符，说明是回文
}
}
![[AIGC] SpringMVC, Filter, Interceptor之间关系详解](https://img-blog.csdnimg.cn/direct/c7ae88b84a6b49eb80c83f3066928483.png)
