public class Solution {
// 题目限定的范围
static int ROW = 5; // y,行,其实对应了 y 坐标
static int COL = 6; // x,列,其实对应了 x 坐标
static int count = 0;
static int[][] visited = new int[100][100];
public static void main(String[] args) {
System.out.println(dfs(4, 4, 5, 4));
}
private static int dfs(int x, int y, int m, int n) {
// 找到它
if (x == m && y == n) {
return 1;
}
// 有效性检查
if (x < 0 || y < 0 || x > COL || y > ROW) {
return 0;
}
// 已经访问过的路口
if (visited[x][y] == 1) {
return 0;
}
visited[x][y] = 1;
// go right
int sum = 0;
sum += dfs(x + 1, y, m, n);
// go down
sum += dfs(x, y - 1, m, n);
// go left
sum += dfs(x - 1, y, m, n);
// go up
sum += dfs(x, y + 1, m, n);
visited[x][y] = 0;
return sum;
}
}
class Solution {
List<String> result = new ArrayList<>();
public List<String> generateParenthesis(int n) {
backtrack("", 0, 0, n);
return result;
}
private void backtrack(String s, int left, int right, int N) {
if (left == N && right == N) {
result.add(s);
return ;
}
if (left < right) {
return;
}
if (left < N) {
backtrack(s + '(', left + 1, right, N);
}
if (right < N) {
backtrack(s + ')', left, right + 1, N);
}
}
}
如果上述 22 题改成如下写法,那么可以看到恢复状态的步骤了:
class Solution {
List<String> result = new ArrayList<>();
public List<String> generateParenthesis(int n) {
backtrack("", 0, 0, n);
return result;
}
private void backtrack(String s, int left, int right, int N) {
if (left == N && right == N) {
result.add(s);
return ;
}
if (left < right) {
return;
}
if (left < N) {
s = s + "(";
backtrack(s, left + 1, right, N);
s = s.substring(0, s.length() - 1);
}
if (right < N) {
s = s + ")";
backtrack(s, left, right + 1, N);
s = s.substring(0, s.length() - 1);
}
}
}