回溯算法的核心思想

  • 选择：从当前状态出发，选择一个可能的候选解。
  • 约束条件：判断当前选择是否满足约束条件。
  • 递归：如果当前选择满足约束条件，递归地进行下一步选择。
  • 回溯：如果当前选择不满足约束条件，或者已经到达问题的解空间的叶子节点，回溯到上一步，尝试其他选择。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void backtrack(状态){
    if(当前状态是解){

        return;
    }
    if(到解空间的叶子节点)return;
    for(每个可能的解){
        if(选择约束条件){
            改变状态;
            backtrack(下一个状态);
            还原状态;
        }
    }
}

排列问题

问题描述：给定一个数组，生成所有可能的排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& result) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue; // 如果当前数字已经被使用，跳过
        path.push_back(nums[i]); // 做出选择
        used[i] = true;
        backtrack(nums, path, used, result); // 递归
        path.pop_back(); // 撤销选择
        used[i] = false;
    }
}

路径之谜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
bool DFS(int x, int y, int n, int m, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;
    if (visited[x][y]) return false;
    if (grid[x][y] == 0) return false; //  0 表示不可通过

    visited[x][y] = true;

    if (x == n - 1 && y == m - 1) {
        return true; // 假设目标点是右下角
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (DFS(nx, ny, n, m, grid, visited)) return true;
    }

    visited[x][y] = false;
    return false;
}