回溯
39.组合总数
难度：⭐️⭐️⭐️
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素 互不相同
- 1 <= target <= 40
解法一 回溯
和全排列一样，使用回溯的经典写法，注意的是，选取的数字一样时算一种解法，所以递归的时候，从index + 1开始。
回溯
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
dfs(candidates, 0, new ArrayList<>(), ans, 0, target);
return ans;
}
private void dfs(int[] candidates, int index, List<Integer> cur, List<List<Integer>> ans, int sum, int target) {
if (sum > target) {
return;
} else if (sum == target) {
ans.add(new ArrayList<>(cur));
} else {
for (int i = index; i < candidates.length; i++) {
if (candidates[i] + sum <= target) {
cur.add(candidates[i]);
dfs(candidates, i, cur, ans, sum + candidates[i], target);
cur.remove(cur.size() - 1);
}
}
}
}
46.全排列
难度：⭐️⭐️⭐️⭐️
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
解法一 回溯
定义递归函数 dfs(first,output) 表示从左往右填到第 first 个位置，当前排列为 output。first左边是已经填充的数，右边是未填充的。小技巧，用元素交换的方式来做标记数组。
核心思想是交换位置。也可以用一个数组标记哪些元素使用过。
时间复杂度：O(n×n!)
空间复杂度：O(n)
回溯
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
List<Integer> output = new ArrayList<>();
for (int num : nums) {
output.add(num);
}
dfs(nums.length, output, 0);
return ans;
}
private void dfs(int n, List<Integer> output, int first) {
if (first == n) {
ans.add(new ArrayList<>(output));
}
for (int i = first; i < n; i++) {
Collections.swap(output, first, i);
dfs(n, output, first + 1);
Collections.swap(output, first, i);
}
}
51.N皇后
难度：⭐️⭐️⭐️⭐️
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
- 1 <= n <= 9
解法一 回溯法 + 数组
要求行、列、同一斜线上不可以有棋子，用3个数组columns、diagonals0、diagonals1分别表示列中、主对角线方向、副对角线方向是否有值。 按行扫描，从第0行开始，尝试在0~n的位置放置棋子，当3个数组都不包含当前位置时，说明该位置是可以放置棋子的，放置棋子，并进入下一行。
时间复杂度：O(n)
空间复杂度：O(1)
集合
class Solution {
private List<List<String>> ans = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
Set<Integer> columns = new HashSet<>();
Set<Integer> diagonals0 = new HashSet<>();
Set<Integer> diagonals1 = new HashSet<>();
int[] queues = new int[n];
Arrays.fill(queues, -1);
solve(queues, 0, columns, diagonals0, diagonals1);
return ans;
}
private void solve(int[] queues, int index, Set<Integer> columns, Set<Integer> diagonals0, Set<Integer> diagonals1) {
int n = queues.length;
if (index == n) {
List<String> matrix = new LinkedList<>();
for (int i = 0; i < n; i++) {
char[] line = new char[n];
Arrays.fill(line, '.');
line[queues[i]] = 'Q';
matrix.add(new String(line));
}
ans.add(matrix);
} else {
for (int i = 0; i < n; i++) {
if (columns.contains(i)) {
continue;
}
if (diagonals0.contains(index - i)) {
continue;
}
if (diagonals1.contains(index + i)) {
continue;
}
queues[index] = i;
columns.add(i);
diagonals0.add(index - i);
diagonals1.add(index + i);
solve(queues, index + 1, columns, diagonals0, diagonals1);
queues[index] = -1;
columns.remove(i);
diagonals0.remove(index - i);
diagonals1.remove(index + i);
}
}
}
}
3 个集合会产生拆装箱的行为，耗时比较多，也可以改成 boolean[]，arr[i] == true 表示第 i 个位置填充的是棋子。注意对角线数组的长度是 2n - 1.
数组
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
int[] queues = new int[n];
Arrays.fill(queues, -1);
dfs(queues, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], result);
return result;
}
private void dfs(int[] queues, int rowIndex, boolean[] column, boolean[] diag0, boolean[] diag1, List<List<String>> result) {
if (rowIndex == queues.length) {
List<String> list = new ArrayList<>(queues.length);
for (int i = 0; i < queues.length; i++) {
char[] row = new char[queues.length];
Arrays.fill(row, '.');
row[queues[i]] = 'Q';
list.add(new String(row));
}
result.add(list);
} else {
for (int i = 0; i < queues.length; i++) {
int d0 = rowIndex + i;
int d1 = rowIndex - i + queues.length - 1;
if (column[i] || diag0[d0] || diag1[d1]) {
continue;
}
queues[rowIndex] = i;
column[i] = true;
diag0[d0] = true;
diag1[d1] = true;
dfs(queues, rowIndex + 1, column, diag0, diag1, result);
queues[rowIndex] = -1;
column[i] = false;
diag0[d0] = false;
diag1[d1] = false;
}
}
}
}
还可以使用int值结合位运算来保存列和对角线上是否出现的元素。
78.子集
难度：⭐️⭐️⭐️⭐️
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解法一 回溯
构建dfs(index, n) 参数表示当前位置是 index，原序列总长度为 index 位置的元素可以选中或不选中，根据该条件递归。
回溯
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
dfs(nums, 0, new ArrayList<>(), result);
return result;
}
private void dfs(int[] nums, int index, List<Integer> sub, List<List<Integer>> result) {
if (index == nums.length) {
result.add(new ArrayList<>(sub));
} else {
// 不选
dfs(nums, index + 1, sub, result);
// 选
sub.add(nums[index]);
dfs(nums, index + 1, sub, result);
sub.remove(sub.size() - 1);
}
}
解法二 位运算
长度为n的数组，一共可以组成2^n个子数组，对于每一位数字，比特位是1认为使用该元素，0认为不使用。
79.单词搜索
难度：⭐️⭐️⭐️⭐️
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true
示例 3：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false
提示：
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
解法一 回溯
类似图的层序遍历，找到匹配的首字母后，向上下左右4个方向搜索，用额外的数组记录当前位置是否被搜索过，然后递归调用。
时间复杂度：O(mn·3L)，L 为 word 的长度
空间复杂度：O(mn)
优化：
- 原地标记，visited 数组可以改成原地标记，遍历前把位置改成特殊字符，比如
#，遍历后恢复，空间复杂度可以减到 O(1) - 字符频率剪枝，先遍历一遍 board 和 word，统计每个字符出现的频率，如果 board 中存在字符的频率比 word 更低，一定无解，直接返回
- 字符串改成CharArray，也能优化一部分时间
回溯
private boolean[][] visited;
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
visited = new boolean[m][n];
char c = word.charAt(0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
boolean found = find(board, i, j, word, 0);
if (found) {
return true;
}
}
}
return false;
}
private boolean find(char[][] board, int x, int y, String word, int index) {
char c = word.charAt(index);
if (board[x][y] != c) {
return false;
}
if (index == word.length() - 1) {
return true;
} else {
visited[x][y] = true;
// left
if (0 < y && !visited[x][y - 1]) {
boolean found = find(board, x, y - 1, word, index + 1);
if (found) {
return true;
}
}
// top
if (0 < x && !visited[x - 1][y]) {
boolean found = find(board, x - 1, y, word, index + 1);
if (found) {
return true;
}
}
// right
if (y + 1 < board[0].length && !visited[x][y + 1]) {
boolean found = find(board, x, y + 1, word, index + 1);
if (found) {
return true;
}
}
// bottom
if (x + 1 < board.length && !visited[x + 1][y]) {
boolean found = find(board, x + 1, y, word, index + 1);
if (found) {
return true;
}
}
visited[x][y] = false;
return false;
}
}
131. 分割回文串
难度：⭐️⭐️⭐️
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
解法一 回溯 + 动态规划
当搜索到第i位置时，s[0, i-1]位置的字符串已经被分成了回文串了，只需要找到下一个位置j，使得s[i, j]也是回文串。回文串用双指针时会有重复计算，使用动态规划，状态转移方程 fn(i, j) = fn(i + 1, j - 1) && s[i] == s[j]。i >= j时，子串长度 <= 1，固定位true。
简单来说，就是通过回溯计算 s 的所有子串，如果是回文串就加到答案中，判断子串是否是回文串，用动态规划，有 2 种方法，一种是直接计算，另一种是根据奇偶从中心扩展。
回溯 + 动态规划
public List<List<String>> partition(String s) {
// dp
boolean[][] dp = new boolean[s.length()][s.length()];
for (int i = s.length() -1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = j - i < 3 || dp[i + 1][j - 1];
}
}
}
// dfs
List<List<String>> result = new ArrayList<>();
dfs(s, 0, dp, new ArrayList<>(), result);
return result;
}
private void dfs(String s, int start, boolean[][] dp, List<String> path, List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(path));
} else {
for (int i = start; i < s.length(); i++) {
if (dp[start][i]) {
path.add(s.substring(start, i + 1));
dfs(s, i + 1, dp, path, result);
path.remove(path.size() - 1);
}
}
}
}