回溯算法
回溯算法思路
回溯算法：本质是递归函数，是穷举的一种方法，在中间添加了每层的执行逻辑和剪枝策略。
回溯算法用于解决：
组合问题：N个数里面按一定规则找出k个数的集合，模板题。
切割问题：一个字符串按一定规则有几种切割方式，注意每次startIndex传递i+1即可，但切割不能排序。
子集问题：一个N个数的集合里有多少符合条件的子集，这是要收集所有节点的结果，每次递归都add进result集合就行。
排列问题：N个数按一定规则全排列，有几种排列方式。注意不能排序。用used数组的树枝去重解即可。
棋盘问题：N皇后，解数独等等。难点本质在剪枝部分。
本质上都是规则一定的情况下，遍历所有可能，但在分步解决问题的时候，可能有些分布不能达成有效的解，就会取消上一步或者上几步的计算，再通过其他可能的分布继续尝试寻找答案。
理解回溯法的关键是一个决策树的遍历过程。
在该决策树中，关键理解以下几点：
- 决策路径：这是纵向的，递归一层就多一个节点。
- 决策选择：这是横向的，在for括号里面定义的选择里，也在单层搜索中的if continue逻辑中，本质就是个剪枝。
回溯算法模板框架：
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
确定递归函数的返回值以及参数。
返回值按照题目的要求，一般是返回一个集合。
参数一般包括题目给的大集合大小n、所求的小集合大小k、startIndex（递增参数，防止出现重复的集合）。
注意：递增参数要配合输入集合的排序使用，因为当终止条件（一般是大于某个值）判断这条路径失败后，就不会执行下面的组合了，因此集合要排序，确保不会遗漏组合。
确定回溯函数的终止条件。
一般是返回集合的大小达到k，就说明找到了一个符合条件的样本。
确定单层搜索的过程。
回溯法的遍历基本都是树形的结构，for循环是用来横向遍历，而递归的过程是纵向遍历。
例如：在解决组合问题时，需要从一系列数字中选择一个数字加入到当前组合中，而For表示从当前的选择集合中选择一个不同的选项。因此，For实际上就是在当前节点的水平层面上进行分支的选择。
一般剪枝都在For括号里边进行剪枝，
一旦做出分支选择，需要继续向下做出更多的决策，递归就是实现重复逻辑操作的函数。
确定如何剪枝操作（难点）。
剪枝就是减少遍历不必要的叶子节点，基本的是再for中的参数进行修改。
如何去重？
- 树枝去重：就是决策路径不能有重复的元素，这里可以用hashset先对输入的集合去重；或者排序后直接跳过重复的元素；或者使用used数组，先排序，在相邻元素相等的情况下，当前一个元素used过，就说明在同一树枝使用过。
- 树层去重：就是决策路径的同一层次不能有重复的元素，可以使用used数组，先排序，在相邻元素相等的情况下，当前一个元素没used过，就说明该元素回溯过，也就是在同一树层使用过。
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
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
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
combineHelper(n, k, 1);
return result;
}
private void combineHelper(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);
combineHelper(n, k, i + 1);
path.removeLast();
}
}
}
|
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
combineSum(n, k, 1, 0);
return result;
}
private void combineSum(int n, int k, int startIndex, int sum){
if(path.size() == k){
if(sum == n){
result.add(new ArrayList<>(path));
return;
}
}
for(int i = startIndex; i <= 9; i++){
path.add(i);
sum += i;
combineSum(n, k, i+1, sum);
path.removeLast();
sum -= i;
}
}
}
|
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 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
33
34
35
36
37
38
39
40
41
42
| class Solution {
List<String> list = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return list;
}
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backTracking(digits, numString, 0);
return list;
}
StringBuilder temp = new StringBuilder();
public void backTracking(String digits, String[] numString, int num) {
if (num == digits.length()) {
list.add(temp.toString());
return;
}
String str = numString[digits.charAt(num) - '0'];
for (int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i));
backTracking(digits, numString, num + 1);
temp.deleteCharAt(temp.length() - 1);
}
}
}
|
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
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
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backTrack(candidates, target, 0, 0);
return result;
}
private void backTrack(int[] candidates, int target,int sum, int startIndex){
if(sum == target){
result.add(new LinkedList<> (path));
return;
}
if(path.size() == 150 || sum > target){
return;
}
for(int i = startIndex; i < candidates.length; i++){
sum += candidates[i];
path.add(candidates[i]);
backTrack(candidates,target, sum, i);
sum -= candidates[i];
path.removeLast();
}
}
}
|
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
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
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
Arrays.sort(candidates);
backTrack(candidates, target, 0, 0);
return result;
}
private void backTrack(int[] candidates, int target,int sum, int startIndex){
if(sum == target){
result.add(new LinkedList<> (path));
return;
}
if(path.size() == 150 || sum > target){
return;
}
for(int i = startIndex; i < candidates.length; i++){
if(i > 0 && !used[i-1] && candidates[i-1] == candidates[i]){
continue;
}
sum += candidates[i];
path.add(candidates[i]);
used[i] = true;
backTrack(candidates,target, sum, i+1);
used[i] = false;
sum -= candidates[i];
path.removeLast();
}
}
}
|
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
思路：先画决策树图，确定横向的决策选择是分割的位置，纵向的决策路径是分割的次数。
- 确定传入参数：s, startIndex，因为不能重复，因此要有startIndex。
- 终止条件：切到不能再切，也就是startIndex达到最右边。
- 单层搜索逻辑：判断是否回文，若是，则放入集合。然后回溯，移出集合。
- 判断回文：双指针左右两边比较。
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
| class Solution {
List<List<String>> lists = new ArrayList<>();
Deque<String> deque = new LinkedList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return lists;
}
private void backTracking(String s, int startIndex) {
if (startIndex >= s.length()) {
lists.add(new ArrayList(deque));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome(s, startIndex, i)) {
String str = s.substring(startIndex, i + 1);
deque.addLast(str);
} else {
continue;
}
backTracking(s, i + 1);
deque.removeLast();
}
}
private boolean isPalindrome(String s, int startIndex, int end) {
for (int i = startIndex, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}
|
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
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
| class Solution {
List<String> result = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder(s);
backTracking(sb, 0, 0);
return result;
}
private void backTracking(StringBuilder s, int startIndex, int dotCount){
if(dotCount == 3){
if(isValid(s, startIndex, s.length() - 1)){
result.add(s.toString());
}
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isValid(s, startIndex, i)){
s.insert(i + 1, '.');
backTracking(s, i + 2, dotCount + 1);
s.deleteCharAt(i + 1);
}else{
break;
}
}
}
private boolean isValid(StringBuilder 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++){
int digit = s.charAt(i) - '0';
num = num * 10 + digit;
if(num > 255)
return false;
}
return true;
}
}
|
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
backTracking(nums, 0);
return result;
}
private void backTracking(int[] nums, int startIndex){
result.add(new ArrayList<>(path));
for(int i = startIndex; i < nums.length; i++){
path.add(nums[i]);
backTracking(nums, i+1);
path.removeLast();
}
}
}
|
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
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 {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
used = new boolean[nums.length];
Arrays.sort(nums);
backTracking(nums, 0);
return result;
}
private void backTracking(int[] nums, int startIndex){
result.add(new ArrayList<> (path));
for(int i = startIndex; i < nums.length; i++){
if(i > 0 && nums[i-1] == nums[i] && !used[i-1]){
continue;
}
path.add(nums[i]);
used[i] = true;
backTracking(nums, i+1);
used[i] = false;
path.removeLast();
}
}
}
|
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
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
| class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backTracking(nums, 0);
return result;
}
private void backTracking(int[] nums, int startIndex){
if(path.size() >= 2)
result.add(new ArrayList<>(path));
HashSet<Integer> hs = new HashSet<>();
for(int i = startIndex; i < nums.length; i++){
if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))
continue;
hs.add(nums[i]);
path.add(nums[i]);
backTracking(nums, i + 1);
path.removeLast;
}
}
}
|
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
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<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0){
return result;
}
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}
private void permuteHelper(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;
}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
|
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
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
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
Arrays.sort(nums);
backTracking(nums);
return result;
}
private void backTracking(int[] nums){
if(path.size() >= nums.length){
result.add(new ArrayList<> (path));
return;
}
for(int i = 0; i < nums.length; i++){
if(i > 0 && !used[i-1] && nums[i-1] == nums[i] || used[i]){
continue;
}
path.add(nums[i]);
used[i] = true;
backTracking(nums);
used[i] = false;
path.removeLast();
}
}
}
|
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
- 例如，行程
["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
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
| class Solution {
private LinkedList<String> res;
private LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
path.add("JFK");
boolean[] used = new boolean[tickets.size()];
backTracking((ArrayList) tickets, used);
return res;
}
public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
if (path.size() == tickets.size() + 1) {
res = new LinkedList(path);
return true;
}
for (int i = 0; i < tickets.size(); i++) {
if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
path.add(tickets.get(i).get(1));
used[i] = true;
if (backTracking(tickets, used)) {
return true;
}
used[i] = false;
path.removeLast();
}
}
return false;
}
}
|
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (char[] c : chessboard) {
Arrays.fill(c, '.');
}
backTrack(n, 0, chessboard);
return res;
}
public void backTrack(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';
backTrack(n, row+1, chessboard);
chessboard[row][col] = '.';
}
}
}
public List Array2List(char[][] chessboard) {
List<String> list = new ArrayList<>();
for (char[] c : chessboard) {
list.add(String.copyValueOf(c));
}
return list;
}
public 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-1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
|
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9 在每一行只能出现一次。
- 数字
1-9 在每一列只能出现一次。
- 数字
1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
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
56
57
58
59
60
61
62
63
64
65
66
67
| class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHelper(board);
}
private boolean solveSudokuHelper(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 (isValidSudoku(i, j, k, board)){
board[i][j] = k;
if (solveSudokuHelper(board)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
private boolean isValidSudoku(int row, int col, char val, char[][] board){
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
for (int j = 0; j < 9; j++){
if (board[j][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;
}
}
|