回溯经典案例
全排列
全排列问题是回溯算法的一个典型应用。它的定义是在给定一个集合（如一个数组或字符串）的情况下，找 出这个集合中元素的所有可能的排列。
question1
1
| 输入一个整数数组，数组中不包含重复元素，返回所有可能的排列。
|
例如：
- [1, 2] ：[1, 2], [2, 1]
- [1, 2, 3] [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 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
| List<Integer> path = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
List<List<Integer>> permutationsI(int[] nums) {
backtrack(nums);
return result;
}
private void backtrack( int[] nums) {
if(path.size() >= nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int num : nums) {
if (!path.contains(num)) {
path.add(num);
backtrack(nums);
path.remove(path.size() - 1);
}
}
}
|
这里使用了列表去重，路径中如果包含当前元素表示已经有添加，直接跳过，这样就避免了 111 122 133 ..... 等排列的形式出现
当然去重的逻辑不止一种，使用布尔值，set 都可以，这里就不展开，感兴趣可以自己尝试。
子集
1
2
3
| 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
|
例如：
- 输入:
nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
回溯代码如下：
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 {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
bfs(0, nums);
return result;
}
public void bfs(int index, int[] nums) {
result.add(new ArrayList<>(path));
if (index >= nums.length) return;
for (int i = index; i < nums.length; i++) {
path.add(nums[i]);
bfs(i + 1, nums);
path.remove(path.size() - 1);
}
}
}
|
N皇后
1
2
| 根据国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。给定 𝑛
个皇后和一个 𝑛 × 𝑛 大小的棋盘，寻找使得所有皇后之间无法相互攻击的摆放方案。
|
八皇后问题可以看作是一个复合的回溯问题，比之一般的回溯问题的限定条件来说 十分复杂 放置每一个棋子（Q）时需要在 行、列、对角线 比较是否有冲突放置，而回溯的地方就是 放置的 ”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
| 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;
}
}
|
