回溯

回溯算法

我觉得这个算法很有意思啊

有点像无限流小说中的那种不断重生探路，死亡回溯，直至找到最佳解法，杀出重围…

依旧插个眼

以后补…

22.括号生成

解：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, n, 0, 0);
        return result;
    }

private:
    void backtrack(vector<string>& result, string& current, int n, int open, int close) {
        if (current.size() == 2 * n) {
            result.push_back(current);
            return;
        }
        // 回溯!
        if (open < n) {
            current.push_back('(');
            backtrack(result, current, n, open + 1, close);
            current.pop_back();
        }

        if (close < open) {
            current.push_back(')');
            backtrack(result, current, n, open, close + 1);
            current.pop_back();
        }
    }
};

路径之谜

剪枝 + 回溯 + DFS

解：

#include <iostream>
#include <vector>
using namespace std;

int n;
int north[15], west[15];
bool visited[15][15]; //格子 (r,c) 是否已走过
vector<int> path;
bool finished = false;

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};

void dfs(int r, int c) {
    if (finished) return;

    path.push_back(r * n + c);
    visited[r][c] = true;
    north[c]--;
    west[r]--;

    if (north[c] < 0 || west[r] < 0) {
        north[c]++;
        west[r]++;
        visited[r][c] = false;
        path.pop_back();
        return;
    }

    if (r == n - 1 && c == n - 1) {
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (north[i] != 0 || west[i] != 0) {
                ok = false;
                break;
            }
        }
        if (ok) {
            finished = true;
            return;
        }
    }
    // dfs + 回溯
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
        if (!visited[nr][nc]) {
            dfs(nr, nc);
            if (finished) return;
        }
    }

    north[c]++;
    west[r]++;
    visited[r][c] = false;
    path.pop_back();
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> north[i];
    for (int i = 0; i < n; i++) cin >> west[i];

    dfs(0, 0);

    for (int x : path) cout << x << " ";
    return 0;
}