什么是回溯
- 一种搜索的方式
- 递归的副产品，只要有递归就会有回溯
- 并非高效算法：本质为穷举
如果使得回溯高效一些呢？
可以使用剪枝的策略去处理，但是本质还是穷举，剪枝只是减少了不必要的穷举方向。
处理问题(只能思考使用暴力解法的问题)：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯法解决的问题都可以抽象为树形结构
同样是三部曲，流程思考
回溯遍历过程大致流程：
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
for循环理解为遍历当前节点的孩子，横向遍历
递归理解为深度，纵向发展
终止条件 —-> 对应到叶子节点
组合类问题
77. 组合
思路：无法暴力for循环，只能考虑使用回溯算法进行处理 类比到树形结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
private LinkedList<Integer> path = new LinkedList<>();
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTrack(n,k,1);
return result;
}
public void backTrack(int n, int k,int startIndex){
if(path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n; i++) {
path.add(i);
backTrack(n,k,i + 1);
path.removeLast();
}
}
}
|
接下来使用剪枝算法进行优化
进行剪枝就是对横向进行减少分支的操作，那么如果是横向操作就是要进行对for循环的截止位置进行处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
private LinkedList<Integer> path = new LinkedList<>();
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTrack(n,k,1);
return result;
}
public void backTrack(int n, int k,int startIndex){
if(path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
backTrack(n,k,i + 1);
path.removeLast();
}
}
}
|
216. 组合总和III
和上题思想一致，只是多出了一个sum = n的限制
对于这题的剪枝操作需要相应的进行修改，这里的同样可以使用上题的思路使用n - (k - path.size()) + 1，但是这里的长度不是n，而是9
需求：组合（a+b+…(k个) = n）
思路：直接递归求解，回溯过程使用一维数组的remove即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
private LinkedList<Integer> path = new LinkedList<>();
private List<List<Integer>> result = new ArrayList<>();
int sum = 0;
public List<List<Integer>> combinationSum3(int k, int n) {
backTrack(k,n,1,sum);
return result;
}
public void backTrack(int k,int n,int startIndex,int sum){
if(sum > n){
return;
}
if(path.size() == k && sum == n){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
sum += i;
path.add(i);
backTrack(k,n,i + 1,sum);
path.removeLast();
sum -= i;
}
}
}
|
电话号码的字母组合
在本题不需要考虑使用startIndex，因为这里不是在一个数组中进行操作的，而是在独立的数组中，所以不需要判断是否出现重复的情况
思路：任意顺序—>组合问题 1.首先让字母和数字对应上 2.digits.length 作为组合length 3.处理for循环中的递归回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
private List<String> result = new ArrayList<>();
StringBuilder sb = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return result;
}
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backTrack(numString,digits,0);
return result;
}
public void backTrack(String[] numString,String digits,int index){
if(sb.length() == digits.length()){
result.add(sb.toString());
return;
}
String str = numString[digits.charAt(index) - '0'];
for (int i = 0; i < str.length(); i++) {
sb.append(str.charAt(i));
backTrack(numString,digits,index + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
|
组合总和
需求：将一个数组转换为树形结构，进行横向纵向遍历，寻找到（a+b…=target） 返回一个二维数组
特殊点：单个数字可重复使用 —> 在纵向遍历中不需要考虑进行i+1的传递
使用了一个组合的和来限制了树的深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
private int sum = 0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backTrack(candidates,target,0,sum);
return result;
}
public void backTrack(int[] candidates, int target,int startIndex,int sum){
if(sum > target){
return;
}
if(sum == target){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; (i < candidates.length) && (sum + candidates[i] <= target); i++) {
path.add(candidates[i]);
sum += candidates[i];
backTrack(candidates,target,i,sum);
path.removeLast();
sum -= candidates[i];
}
}
}
|
40.组合总和II
思路：和上题思路几乎一致，区别就在于元素不可以重复使用 那么对应的操作就是在纵向遍历时考虑到i+1
特征：本题数组中会出现相同的元素 —-> 数组去重操作
思路优化：首先去重，之后操作一致考虑递归index+1
去重思路：考虑不同的去重情况 去重可能出现树层，也可能出现在树枝 在递归的过程中是允许出现相同的元素的，这是树枝，但是在for循环 横向遍历时是不允许出现相同于元素进行二次组合的，这是树层。
那么具体如何实现判断在去重时是在树层还是树枝呢？ 使用一个数组，进行判断，如果使用过，则将下标处设置为1，若未使用则设置为0
整个数组是有序的，判断时如果该数组下标为0则说明此时该相同元素未被使用过，则说明这并非是递归过程中的相同元素，那么此时就该将此层跳过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
private int sum = 0;
boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
Arrays.fill(used,false);
Arrays.sort(candidates);
backTrack(candidates,target,0,sum);
return result;
}
public void backTrack(int[] candidates, int target,int startIndex,int sum){
if(sum > target){
return;
}
if(sum == target){
result.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]){
continue;
}
path.add(candidates[i]);
sum += candidates[i];
used[i] = true;
backTrack(candidates,target,i + 1,sum);
path.removeLast();
sum -= candidates[i];
used[i] = false;
}
}
}
|
也可以不去使用一个额外数组进行判断是否使用，这里的目的就是判断在树层是否使用过，未使用即在for循环中已经跳过了这个元素，所以也可以只判断i是否在当前树层节点之后
方式二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
private int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backTrack(candidates,target,0);
return result;
}
public void backTrack(int[] candidates, int target,int startIndex){
if(sum > target){
return;
}
if(sum == target){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; (i < candidates.length) && (sum + candidates[i] <= target); i++) {
if(i > startIndex && candidates[i-1] == candidates[i]){
continue;
}
path.add(candidates[i]);
sum += candidates[i];
backTrack(candidates,target,i + 1);
path.removeLast();
sum -= candidates[i];
}
}
}
|
分割类问题
131.分割回文串
这题乍一看有点像之前的有一题滑动窗口问题，就是类似特征，需要进行多次更改截止位置和初始位置，但是当时那题是使用sum将窗口进行绑定，而这题如果使用滑动窗口的化没有办法将元素绑定起来进行共同移动，那为什么当时那题不去思考使用回溯算法呢？因为数组length过大，使用回溯必然超时，而这题最大是16 则可以使用回溯算法
思维断点：
- 可视化为树形结构 理解其构造
- 使用index 模拟切割线位置
终止条件是 起始位置大于s的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
private List<List<String>> result = new ArrayList<>();
private LinkedList<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
backTrack(s,0);
return result;
}
public void backTrack(String s,int startIndex){
if(startIndex >= s.length()){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex;i < s.length(); i++) {
if(isPalindrome(s,startIndex,i)){
path.add(s.substring(startIndex,i + 1));
}else {
continue;
}
backTrack(s,i + 1);
path.removeLast();
}
}
public boolean isPalindrome(String s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}
|
93.复原IP地址
本题和上题类似，唯一的区别就在于需要考虑额外的限制条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
private List<String> result = new ArrayList<>();
private StringBuilder sb = new StringBuilder();
public List<String> restoreIpAddresses(String s) {
if (s.length() > 12) return result;
backTrack(s,0,0);
return result;
}
public void backTrack(String s, int startIndex, int point){
if (point == 3) {
if (isValid(s,startIndex,s.length()-1)) {
result.add(s);
}
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isValid(s, startIndex, i)) {
s = s.substring(0, i + 1) + "." + s.substring(i + 1);
backTrack(s, i + 2, point+1);
s = s.substring(0, i + 1) + s.substring(i + 2);
} else {
break;
}
}
}
public boolean isValid(String s,int start,int end){
if (start > end) {
return false;
}
if (s.charAt(start) == '0' && start != end) {
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s.charAt(i) > '9' || s.charAt(i) < '0') {
return false;
}
num = num * 10 + (s.charAt(i) - '0');
if (num > 255) {
return false;
}
}
return true;
}
}
|
子集类问题
本类型问题和组合问题存在的巨大区别就在于如何收获结果
组合问题：均为叶子节点上获取结果
而子集问题是：路径上的节点同样是需要的 所以和之前逻辑存在出入的就是获取结果的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
backTrack(nums,0);
return result;
}
public void backTrack(int[] nums,int startIndex){
result.add(new ArrayList<>(path));
if(startIndex >= nums.length){
return;
}
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backTrack(nums,i + 1);
path.removeLast();
}
}
}
|
90.子集II
和上题主要区别在于本题给出数组是存在重复元素的，所以需要进行在树层进行（即for循环过程中）进行去重处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backTrack(nums,0);
return result;
}
public void backTrack(int[] nums,int startIndex){
result.add(new ArrayList<>(path));
if(startIndex >= nums.length){
return;
}
for (int i = startIndex; i < nums.length; i++) {
if(i > startIndex && nums[i - 1] == nums[i]){
continue;
}
path.add(nums[i]);
backTrack(nums,i + 1);
path.removeLast();
}
}
}
|
491.递增子序列
需求：返回数组元素递增子序列 处理存在于纵向遍历的过程中
思路：本题同样需要进行去重处理，但是不能改变数组顺序 所以可以使用一个哈希表在树层遍历的时候添加一个判断是否存在 同时每一次都需要判断这个数组的最右边的值是否小于即将添加的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backTrack(nums,0);
return result;
}
public void backTrack(int[] nums,int startIndex){
if(path.size() >= 2) {
result.add(new ArrayList<>(path));
}
if(startIndex >= nums.length){
return;
}
int[] used = new int[201];
for (int i = startIndex; i < nums.length; i++) {
if((!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || used[nums[i] + 100] == 1){
continue;
}
path.add(nums[i]);
used[nums[i] + 100] = 1;
backTrack(nums,i + 1);
path.removeLast();
}
}
}
|
排列类问题
46.全排列
思路：返回所有结果，这和组合类似，区别在于for循环横向遍历过程中，不需要排除
思维断点：判断是否使用的方式以及终止条件（排列是需所有元素都在其中）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
Arrays.fill(used,false);
backTrack(nums);
return result;
}
public void backTrack(int[] nums){
if (path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if(used[i]){
continue;
}
path.add(nums[i]);
used[i] = true;
backTrack(nums);
path.removeLast();
used[i] = false;
}
}
}
|
47.全排列 II
需求：相比上题直接求解多出一个去重的逻辑 树层去重
这里的去重逻辑可以考虑使用之前处理组合问题的逻辑，数组顺序可变，在纵向遍历上需要上一个相同元素被使用过，若未使用则continue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
Arrays.fill(used,false);
Arrays.sort(nums);
backTrack(nums);
return result;
}
public void backTrack(int[] nums){
if (path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if(used[i]){
continue;
}
if(i > 0 && !used[i-1] && nums[i-1] == nums[i]){
continue;
}
path.add(nums[i]);
used[i] = true;
backTrack(nums);
path.removeLast();
used[i] = false;
}
}
}
|
但是会出现一种情况就是used[i - 1] == false也行而used[i - 1] == true都可以提交通过，很离谱是吧，但是如果去做个树形结构分析之后可以发现，其实后者出现了很多无用搜索
当然这里可以考虑使用set数组去做层间判断是否存在，但是时间复杂度和空间复杂度都远大于used数组去操作
使用used数组是O(n + n)还是O(n)，但如果是set数组去判断是否存在则会变成O(n^2)的时间复杂度
棋盘类问题
51. N皇后
需求：最终返回为一个三维数组，其中放置多个棋盘
单层处理逻辑是需要考虑到摆放 横竖斜不能存在第二个Q
终止条件：row == n
主要难点在于如何对二维进行判断处理细节以及考虑到使用回溯解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
private List<List<String>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (char[] chars : chessboard) {
Arrays.fill(chars,'.');
}
backTrack(n,0,chessboard);
return result;
}
public void backTrack(int n,int row,char[][] chessboard){
if(row == n){
result.add(arrayTolist(chessboard));
return;
}
for (int i = 0; i < n; i++) {
if(isValid(i,row,chessboard,n)){
chessboard[row][i] = 'Q';
backTrack(n,row + 1,chessboard);
chessboard[row][i] = '.';
}
}
}
public List<String> arrayTolist(char[][] chessboard) {
List<String> list = new ArrayList<>();
for (char[] chars : chessboard) {
list.add(String.valueOf(chars));
}
return list;
}
public boolean isValid(int col,int row,char[][] chessboard,int n){
for (int j = 0; j < row; j++) {
if(chessboard[j][col] == 'Q'){
return false;
}
}
for (int i = col - 1,j = row - 1; i >= 0 && j >= 0 ; i-- ,j--) {
if(chessboard[j][i] == 'Q'){
return false;
}
}
for (int i = col + 1,j = row - 1; i <= n-1 && j >= 0; i++,j--) {
if(chessboard[j][i] == 'Q'){
return false;
}
}
return true;
}
}
|
37. 解数独
区别在哪？判断合法放置方式改变
但这并不是主要区别
主要区别是本题的维度发生了变化，是一个二维递归，使用两层for循环嵌套了这个这个判断过程，进行填数处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public void solveSudoku(char[][] board) {
boolean judge = backTrack(board);
}
public boolean backTrack(char[][] board){
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if(board[i][j] == '.'){
for (char k = '1'; k <= '9'; k++) {
if(isValid(board,i,j,k)){
board[i][j] = k;
if(backTrack(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board,int row,int col,char num){
for (int i = 0; i < 9; i++){
if (board[row][i] == num){
return false;
}
}
for (int j = 0; j < 9; j++){
if (board[j][col] == num){
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] == num){
return false;
}
}
}
return true;
}
}
|
其它类型
332.重新安排行程
深度搜索问题，也可以考虑使用回溯去做，这题的特征就是深度搜索
这题需要明确三件事
- 返回值是什么
- 终止条件
- 单层逻辑
逻辑链：由深度搜索首先想到将其视为回溯进行处理的问题 》》 进行树状分析 》》 考虑题中出现的需求是按照字母序排列思考使用的容器(C++需要考虑容器，在Java中对于String类List可以使用创建构造器使用CampareTo方法)
按照之前的逻辑写，去重只需要保证当前票未被使用即可 穷举所有路径的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
List<String> path = new ArrayList<>();
List<List<String>> result = new ArrayList<>();
boolean[] used = new boolean[301];
boolean find;
public List<String> findItinerary(List<List<String>> tickets) {
tickets.sort(((o1, o2) -> o1.get(1).compareTo(o2.get(1))));
path.add("JFK");
backTrack(tickets);
return result.get(0);
}
public void backTrack(List<List<String>> tickets){
if(find){
return;
}
if(tickets.size() + 1 == path.size()){
find = true;
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < tickets.size(); i++) {
if(tickets.get(i).get(0).equals(path.get(path.size() - 1)) && !used[i]){
path.add(tickets.get(i).get(1));
used[i] = true;
backTrack(tickets);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
}
|
