回溯算法练习
回溯（Backtracking）是一种通过递归在决策树中执行深度优先搜索（DFS）来寻找所有解的算法。其核心是状态重置。
46. 全排列 (Permutations)
题目描述
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以 按任意顺序 返回答案。
解题思路
典型的回溯模板。维护一个 used 数组或通过交换 swap 的方式，标记哪些数已经被加入当前排列。
Java 代码实现
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path)); return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; path.add(nums[i]);
backtrack(nums, used, path, res);
path.remove(path.size() - 1); used[i] = false;
}
}
}
78. 子集 (Subsets)
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解题思路
对于每个元素，有两种选择：选或不选。或者采取：在每一层循环中，从当前索引 start 开始向下探索，并将每一条路径作为子集。
Java 代码实现
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, new ArrayList<>(), res);
return res;
}
private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(i + 1, nums, path, res);
path.remove(path.size() - 1);
}
}
}
17. 电话号码的字母组合 (Letter Combinations of a Phone Number)
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
解题思路
利用哈希表映射数字与字母的关系。递归地遍历输入的每一位数字及其对应的字母列表。
Java 代码实现
class Solution {
private String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits.length() == 0) return res;
backtrack(digits, 0, new StringBuilder(), res);
return res;
}
private void backtrack(String digits, int idx, StringBuilder sb, List<String> res) {
if (idx == digits.length()) {
res.add(sb.toString()); return;
}
String letters = map[digits.charAt(idx) - '0'];
for (char c : letters.toCharArray()) {
sb.append(c);
backtrack(digits, idx + 1, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}
}
39. 组合总和 (Combination Sum)
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。 candidates 中的 同一个 数字可以 无限制重复被选取 。
解题思路
关键在于允许元素重复使用。在递归调用时，start 索引保持当前 i，而不加一。如果 target < 0 就剪枝。
Java 代码实现
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, target, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path)); return;
}
for (int i = start; i < candidates.length; i++) {
if (target - candidates[i] < 0) break;
path.add(candidates[i]);
backtrack(candidates, target - candidates[i], i, path, res);
path.remove(path.size() - 1);
}
}
}
22. 括号生成 (Generate Parentheses)
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
解题思路
维护当前 left（已使用的左括号数）和 right（已使用的右括号数）。
- 如果
left < n，可以放左括号。 - 如果
right < left，可以放右括号。
Java 代码实现
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(res, new StringBuilder(), 0, 0, n);
return res;
}
private void backtrack(List<String> res, StringBuilder sb, int left, int right, int n) {
if (sb.length() == n * 2) {
res.add(sb.toString()); return;
}
if (left < n) {
sb.append('('); backtrack(res, sb, left + 1, right, n); sb.deleteCharAt(sb.length() - 1);
}
if (right < left) {
sb.append(')'); backtrack(res, sb, left, right + 1, n); sb.deleteCharAt(sb.length() - 1);
}
}
}
79. 单词搜索 (Word Search)
题目描述
给定一个 m x n 二维网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
解题思路
对于网格中的每个点，启动 DFS 搜索。每次探索四个方位。利用原地修改 '#' 来标记已访问状态，搜索结束后回溯。
Java 代码实现
class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, 0, i, j)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int idx, int r, int c) {
if (idx == word.length()) return true;
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(idx)) return false;
char tmp = board[r][c];
board[r][c] = '#';
boolean res = dfs(board, word, idx + 1, r + 1, c) || dfs(board, word, idx + 1, r - 1, c) ||
dfs(board, word, idx + 1, r, c + 1) || dfs(board, word, idx + 1, r, c - 1);
board[r][c] = tmp;
return res;
}
}
131. 分割回文串 (Palindrome Partitioning)
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
解题思路
遍历字符串，对于每一个起点，切割出一个前缀子串。如果是回文串，则递归处理后续部分。
Java 代码实现
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
if (start == s.length()) {
res.add(new ArrayList<>(path)); return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
path.add(s.substring(start, i + 1));
backtrack(s, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int L, int R) {
while (L < R) if (s.charAt(L++) != s.charAt(R--)) return false;
return true;
}
}
51. N 皇后 (N-Queens)
题目描述
按照国际象棋的规则，皇后可以攻击与并在同一行、同一列或同一对角线上的棋子。 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
解题思路
按行回溯。在每一行挑选一个没有冲突的列。记录 cols, diagonals1, diagonals2（对角线：r-c 恒定或 r+c 恒定）来进行 O(1) 的冲突检测。
Java 代码实现
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
backtrack(board, 0, res);
return res;
}
private void backtrack(char[][] board, int row, List<List<String>> res) {
if (row == board.length) {
res.add(construct(board)); return;
}
for (int col = 0; col < board.length; col++) {
if (!isValid(board, row, col)) continue;
board[row][col] = 'Q'; backtrack(board, row + 1, res); board[row][col] = '.';
}
}
private boolean isValid(char[][] board, int r, int c) {
for (int i = 0; i < r; i++) {
if (board[i][c] == 'Q') return false;
}
for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
for (int i = r - 1, j = c + 1; i >= 0 && j < board.length; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
private List<String> construct(char[][] board) {
List<String> l = new ArrayList<>();
for (char[] row : board) l.add(new String(row));
return l;
}
}