回溯算法总结
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，就构成的树的深度。
回溯函数遍历过程伪代码如下：
for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
总结：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
1 组合问题
// 要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。
// 77. 组合
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTracking(n,k,1);
return res;
}
private void backTracking(int n,int k,int startIndex) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n; i++) {
path.add(i);
backTracking(n,k,i + 1);
path.remove(path.size() - 1);
}
}
}
// 优化算法
/*
优化过程如下：
已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。
*/
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTracking(n,k,1);
return res;
}
private void backTracking(int n,int k,int startIndex) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 剪枝
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
backTracking(n,k,i + 1);
path.remove(path.size() - 1);
}
}
}
// 216. 组合总和 III
// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n,k,0,1);
return res;
}
private void backTracking(int targetSum,int k,int tmpSum,int startIndex) {
if (path.size() == k) {
if (targetSum == tmpSum) {
res.add(new ArrayList<>(path));
}
}
for (int i = startIndex; i <= 9; i++) {
path.add(i);
tmpSum += i;
backTracking(targetSum,k,tmpSum,i + 1);
tmpSum -= i;
path.remove(path.size() - 1);
}
}
}
// 本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而回溯算法：求组合问题！和回溯算法：求组合总和！都是是求同一个集合中的组合
// 17. 电话号码的字母组合
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
class Solution {
private String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> res = new ArrayList<>();
private StringBuilder sb = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return res;
}
backTracking(digits,0);
return res;
}
private void backTracking(String digits, int num) {
if (num == digits.length()) {
res.add(sb.toString());
return;
}
String str = numString[digits.charAt(num) - '0'];
for (int i = 0; i < str.length(); i++) {
sb.append(str.charAt(i));
backTracking(digits,num + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
// 39. 组合总和
// 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backTracking(candidates,target,0,0);
return res;
}
private void backTracking(int[] candidates,int target,int sum,int startIndex) {
if (sum > target) return;
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
path.add(candidates[i]);
sum += candidates[i];
backTracking(candidates,target,sum,i);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
//剪枝
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//排序
Arrays.sort(candidates);
backTracking(candidates,target,0,0);
return res;
}
private void backTracking(int[] candidates,int target,int sum,int startIndex) {
if (sum > target) return;
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
//剪枝
for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
path.add(candidates[i]);
sum += candidates[i];
backTracking(candidates,target,sum,i);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
// 40. 组合总和 II
// 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
boolean[] used = new boolean[candidates.length];
Arrays.sort(candidates);
backTracking(candidates,target,0,0,used);
return res;
}
private void backTracking(int[] candidates,int target,int sum,int startIndex,boolean[] used) {
if (sum > target) return;
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == false) {
continue;
}
used[i] = true;
path.add(candidates[i]);
sum += candidates[i];
backTracking(candidates,target,sum,i + 1,used);
sum -= candidates[i];
path.remove(path.size() - 1);
used[i] = false;
}
}
}
2 分割问题
思路：切割问题其实是一种组合问题。递归用来纵向遍历，for循环用来横向遍历，切割线切割到字符串的结尾位置，说明找到了一个切割方法。
// 131. 分割回文串
// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
class Solution {
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
backTracking(s,0);
return res;
}
private void backTracking(String s,int startIndex) {
if (startIndex >= s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome(s,startIndex,i)) {
String subStr = s.substring(startIndex,i + 1);
path.add(subStr);
} else {
continue;
}
backTracking(s,i + 1);
path.remove(path.size() - 1);
}
}
private boolean isPalindrome(String s,int left,int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
}
// 93. 复原 IP 地址
// 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
class Solution {
private List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if (s.length() > 12) return res;
backTracking(s,0,0);
return res;
}
private void backTracking(String s,int startIndex,int pointNum) {
if (pointNum == 3) {
if (isValided(s,startIndex,s.length() - 1)) {
res.add(s);
}
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isValided(s,startIndex,i)) {
s = s.substring(0,i + 1) + "." + s.substring(i + 1);
pointNum++;
backTracking(s,i + 2,pointNum);
pointNum--;
s = s.substring(0,i + 1) + s.substring(i + 2);
} else {
break;
}
}
}
private boolean isValided(String s,int start,int end) {
if (start > end) return false;
if (s.charAt(start) == '0' && start != end) return false;
int sum = 0;
for (int i = start; i <= end; i++) {
if (s.charAt(i) > '9' || s.charAt(i) < '0') return false;
sum = sum * 10 + (s.charAt(i) - '0');
if (sum > 255) {
return false;
}
}
return true;
}
}
3 子集问题
思路：如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
// 78. 子集
// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if (nums == null || nums.length == 0) return res;
backTracking(nums,0);
return res;
}
private void backTracking(int[] nums,int startIndex) {
res.add(new ArrayList<>(path));
if (startIndex >= nums.length) {
return;
}
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backTracking(nums,i + 1);
path.remove(path.size() - 1);
}
}
}
// 90. 子集 II
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums == null && nums.length == 0) return res;
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backTracking(nums,0,used);
return res;
}
private void backTracking(int[] nums,int startIndex,boolean[] used) {
res.add(new ArrayList<>(path));
if (startIndex >= nums.length) return;
for (int i = startIndex; i < nums.length; i++) {
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {
continue;
}
path.add(nums[i]);
used[i] = true;
backTracking(nums,i + 1,used);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
4 排列问题
思路：
- 每层都是从0开始搜索而不是startIndex
- 需要used数组记录path里都放了哪些元素了
- 组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
// 46. 全排列
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0) return res;
used = new boolean[nums.length];
backTracking(nums);
return res;
}
private void backTracking(int[] nums) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] == true) continue;
used[i] = true;
path.add(nums[i]);
backTracking(nums);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
// 47. 全排列 II
// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0) return res;
used = new boolean[nums.length];
Arrays.sort(nums);
backTracking(nums);
return res;
}
private void backTracking(int[] nums) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] == true) continue;
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) continue;
used[i] = true;
path.add(nums[i]);
backTracking(nums);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
5 棋盘问题
// 二维矩阵中矩阵的高就是这颗树的高度，矩阵的宽就是树形结构中每一个节点的宽度。我们用皇后们的约束条件，来回溯搜索这颗树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。
// 51. N 皇后
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
class Solution {
private List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessBoard = new char[n][n];
for (char[] chs : chessBoard) {
Arrays.fill(chs,'.');
}
backTracking(n,0,chessBoard);
return res;
}
private void backTracking(int n,int row,char[][] chessBoard) {
if (row == n) {
res.add(Array2List(chessBoard));
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row,col,n,chessBoard)) {
chessBoard[row][col] = 'Q';
backTracking(n,row + 1,chessBoard);
chessBoard[row][col] = '.';
}
}
}
private boolean isValid(int row,int col,int n, char[][] chessBoard) {
for (int i = 0; i < row; i++) {
if (chessBoard[i][col] == 'Q') return false;
}
for (int i = row - 1,j = col - 1; i >=0 && j>=0; i--,j--) {
if (chessBoard[i][j] == 'Q') return false;
}
for (int i = row - 1,j = col + 1; i>=0 && j<n; i--,j++) {
if (chessBoard[i][j] == 'Q') return false;
}
return true;
}
private List<String> Array2List(char[][] chessBoard) {
List<String> path = new ArrayList<>();
for (char[] chs : chessBoard) {
path.add(String.valueOf(chs));
}
return path;
}
}
// 因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性。
// 37. 解数独
// 编写一个程序，通过填充空格来解决数独问题。
// 数独的解法需 遵循如下规则：
// 数字 1-9 在每一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
// 数独部分空格内已填入了数字，空白格用 '.' 表示。
class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHandler(board);
}
private boolean solveSudokuHandler(char[][] board) {
for (int i = 0; i <9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') continue;
for (char k = '1'; k <= '9'; k++) {
if (isValid(i,j,k,board)) {
board[i][j] = k;
if(solveSudokuHandler(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
private boolean isValid(int row,int col,char val,char[][] board) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == val) {
return false;
}
}
for (int i = 0; i < 9; i++) {
if (board[i][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val) {
return false;
}
}
}
return true;
}
}
6 其他问题
// 491. 递增子序列
// 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
if (nums == null || nums.length == 0) return res;
backTracking(nums,0);
return res;
}
private void backTracking(int[] nums,int startIndex) {
if (path.size() > 1) {
res.add(new ArrayList<>(path));
}
boolean[] used = new boolean[201];
for (int i = startIndex; i < nums.length; i++) {
if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || used[nums[i] + 100] == true) {
continue;
}
used[nums[i] + 100] = true;
path.add(nums[i]);
backTracking(nums,i + 1);
path.remove(path.size() - 1);
}
}
}
