回溯 - YYKK的笔记本

在小范围的数据中尝试对一个复杂的状态求解

一种可以退回上一个（几个）状态的，用递归实现的枚举

1.组合

// 老版 c++

vector<vector<int>> ans;
vector<int> comb; // 状态
int n, k;

void traceback() {
    if (comb.size() == k) {
        // 检测是否达到目标
        ans.push_back(comb);
        return;
    }
    int lower = comb.size() == 0 ? 1 : comb.back() + 1;
    for (int i = lower; i <= n; i++) { // 状态转移
        comb.push_back(i); // 更新状态
        traceback();
        comb.pop_back(); // 回滚状态
    }
}

int main() {
    cin >> n >> k;
    traceback();
}

// 现代化 c++

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> ans;
    vector<int> comb;

    auto traceback = [&](auto &self) {
        if (comb.size() == k) {
            ans.push_back(comb);
            return;
        }
        int lower = comb.size() == 0 ? 1 : comb.back() + 1;
        for (int i = lower; i <= n; i++) {
            comb.push_back(i);
            self(self);
            comb.pop_back();
        }
    };

    traceback(traceback);
}

在函数递归中，return 是结束本次的函数，返回上一层的函数，而不是结束所有函数（结束当前函数）

有几次从self(self)处进入下一个递归,最后退出时就有几个执行self(self)下面那条语句(一般是pop_back(),所以会有大量退出去连续pop_back(),从而连续回滚多个状态)

2.全排列(是否包含重复元素)

    vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;
     int n = nums.size();
     vector<vector<int>> ans;
     vector<int> perm;
     vector<int> used(n);
     auto traceback = [&](auto &self) {
       if (perm.size() == n) {
         ans.push_back(perm);
         return;
       }
       for (int i = 0; i < n; i ++) {
         if (used[i]) continue;
         perm.push_back(nums[i]);
         used[i] = true;
         self(self);
         used[i] = false;
         perm.pop_back();
       }
     };
     traceback(traceback);
     return ans;

理解嵌套在for循环中的递归(这个i是均匀变化的)

  sort(nums.begin(), nums.end());
  do {
      ans.push_back(nums);
    } while (next_permutation(nums.begin(), nums.end()));
    return ans;

排序也可以分大小的

最小nums = [1, 2, 3]

最大nums = [3, 2, 1]

next_permutation 把 nums 原地修改成“下一个字典序排列”。

配合sort(使得最开始的排序是最小的排序])就可以按排列数的字典序从小到大获取所有的排列

通常配合 do-while 循环使用，来遍历一个序列的所有可能排列（前提是初始序列必须是最小排列，所以一般会先 sort）。

3.组合总和

class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
    vector<vector<int>> ans;
    vector<int> comb;
    auto traceback = [&](auto &self, int lower, int sum) {
        if (sum == target) {
            ans.push_back(comb);
            return;
        }
        for (int i = lower; i < candidates.size(); i ++) {
            if (sum + candidates[i] > target) continue;
            comb.push_back(nums[i]);
            self(self, i, sum + candidates[i]);
            comb.pop_back();
        }
    };
    traceback(traceback, 0, 0);
    return ans;
}
};

这里定义了i = lower,并在之后把i作为lower传入了,那么这里就可以继承i在上一次递归中的值(和全排列相比),也是一种写法

N皇后的坐标映射问题

1.如何映射矩阵中两条斜对角线的坐标到一维数组中

2.没有考虑在多维数组中进行多向搜索的问题,而是因为反正都是一站站一行一列,两条对角线,直接转化为了判断是否存在的问题,不用像搜索算法那样判断复杂地块的问题.

数组接龙

dir是按所给方向顺序编写的,所以ans += d + '0';才能正确统计答案.

路径不重合时需要判断两条路线是否交叉,传统的数据结构比较难以判断,可以把数组扩大一倍,来判断有没有走过中间的格子

  auto maze = vector(n * 2, vector(n * 2, 0));
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < n; j ++) {
      cin >> maze[i * 2][j * 2];
    }
  }

1.A 尝试方向 0：走到 B。
- ◦B 尝试方向 0：走到 C。
  - ▪C 尝试方向 0：走到 D。
    •D 是死路，返回 false 给 C。
  - ▪C 收到 false，撤销方向 0（恢复状态）。
  - ▪C 尝试方向 1：如果也是死路，返回 false 给 B。
- ◦B 收到 false，撤销方向 0，继续尝试方向 1……
- ◦如果 B 的所有方向都失败，返回 false 给 A。

2.A 收到 false，撤销方向 0，尝试方向 1……

3.直到找到一条通路，或者确认无解。

#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;

vector<pair<int, int>> dir = {
  {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}
};
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  auto maze = vector(n * 2, vector(n * 2, 0));
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < n; j ++) {
      cin >> maze[i * 2][j * 2];
    }
  }
  auto vis = vector(n * 2, vector(n * 2, 0));
  string ans;
  auto inside = [&](int x, int y) {
    return x >= 0 && x < n * 2 && y >= 0 && y < n * 2;
  };
  auto traceback = [&](auto &self, int x, int y) {
    // if (ans.size() == 6) {
    //   cout << ans << endl;
    // }
    if (x == n * 2 - 2 && y == n * 2 - 2) {
      if ((int)ans.size() == n * n - 1) return true;//唯一成功出口，表示找到了一个完整且合法的路径
      return false;//过早到达终点，步数不够
    }
    for (int d = 0; d < 8; d ++) {
      auto [dx, dy] = dir[d];
      int nx = x + dx, ny = y + dy;
      int nnx = nx + dx, nny = ny + dy;
      if (!inside(nnx, nny)) continue;
      if (vis[nx][ny] || vis[nnx][nny]) continue;
      if (maze[nnx][nny] != (maze[x][y] + 1) % k) continue;
      vis[nx][ny] = vis[nnx][nny] = true;
      ans += d + '0';
      if (self(self, nnx, nny)) return true;//在更深层的搜索中，已经找到了完整通路.不再执行后面的 pop_back 和 vis 恢复，也不继续尝试当前格子的其他方向。
      ans.pop_back();
      vis[nx][ny] = vis[nnx][nny] = false;
    }
    //for 循环全部执行完毕，但 if (self(...)) return true; 从未被执行。
    return false;//当前格子尝试了所有 8 个方向，每一个方向都走不通 // “每一个方向都走不通” 已经包含了该方向的深层递归
  };
  vis[0][0] = 1;
  if (maze[0][0] == 0 && traceback(traceback, 0, 0)) {
    cout << ans << endl;
  } else {
    cout << -1 << endl;
  }
}