// 回溯,时间复杂度O(MN*3的L次方),空间复杂度O(MN),M、N分别是board的行数、列数；L是word的长度
public boolean exist(char[][] board, String word) {
    int h = board.length, w = board[0].length;
    // 创建一个二维布尔数组用于记录当前位置是否被访问过
    boolean[][] visited = new boolean[h][w];
    // 遍历二维数组
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            // 调用check方法检查当前位置是否可以匹配word字符串的第一个字符，如果可以则继续
            boolean flag = check(board, visited, i, j, word, 0);
            if (flag) {
                return true;
            }
        }
    }
    // 如果没有匹配成功，返回false
    return false;
}

public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
    // 如果当前字符不等于字符串s的第k个字符，返回false
    if (board[i][j] != s.charAt(k)) {
        return false;
    } else if (k == s.length() - 1) {
        // 如果字符串s的所有字符都匹配，返回true
        return true;
    }
    // 标记当前位置被访问
    visited[i][j] = true;
    // 定义4个方向
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    boolean result = false;
    // 遍历4个方向
    for (int[] dir : directions) {
        int newi = i + dir[0], newj = j + dir[1];
        if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
            // 新的位置没有被访问
            if (!visited[newi][newj]) {
                // 递归调用check函数
                boolean flag = check(board, visited, newi, newj, s, k + 1);
                // 如果匹配，返回true
                if (flag) {
                    result = true;
                    break;
                }
            }
        }
    }
    // 标记当前位置没有被访问
    visited[i][j] = false;
    return result;
}

SIZE = 5


def show_board(board, totals=[0]):
    """显示棋盘和第几种走法"""
    totals[0] += 1
    print(f'第{totals[0]}种走法: ')
    for row in board:
        for col in row:
            print(str(col).center(4), end='')
        print()


def patrol(board, row=0, col=0, step=1):
    """用递归回溯的方式搜索所有的巡逻方式
    :param board: 棋盘（用嵌套列表表示）
    :param row: 骑士准备巡逻的位置对应的行
    :param col: 骑士准备巡逻的位置对应的列
    :param step: 序号（按巡逻的顺序依次标记）
    """
    if row >= 0 and row < SIZE and col >= 0 and col < SIZE and board[row][col] == 0:
        # 如果row和col都在棋盘范围以内且对应的格子没有巡逻过就标记它
        board[row][col] = step
        if step == SIZE * SIZE:
            # 所有的格子都被标记（一次巡逻完成）就输出棋盘
            show_board(board)
        # 向下一个格子继续巡逻（国际象棋的骑士可以往八个方向进行）
        # 巡逻方向不同row和col的变化就不同，但step都是统一加1
        patrol(board, row - 2, col - 1, step + 1)
        patrol(board, row - 1, col - 2, step + 1)
        patrol(board, row + 1, col - 2, step + 1)
        patrol(board, row + 2, col - 1, step + 1)
        patrol(board, row + 2, col + 1, step + 1)
        patrol(board, row + 1, col + 2, step + 1)
        patrol(board, row - 1, col + 2, step + 1)
        patrol(board, row - 2, col + 1, step + 1)
        # 八个方向都行不通或者所有格子已经巡逻完毕就回到上一步（回溯）
        # 回溯时要记得清除之前标记的step，标记为0相当于格子未被巡逻
        board[row][col] = 0


def main():
    # 初始化棋盘（每个格子都标为0表示没有巡逻过）
    board = [[0] * SIZE for _ in range(SIZE)]
    patrol(board)


if __name__ == '__main__':
    main()

#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

const int SIZE = 5;

void show_board(const vector<vector<int> >& board) {
    static int total = 0;
    cout << "第" << ++total << "种走法: " << endl;
    for (const auto& row : board) {
        for (const auto& col : row) {
            cout << setw(4) << col;
        }
        cout << endl;
    }
}

void patrol(vector<vector<int> >& board, int row = 0, int col = 0, int step = 1) {
    if (row >= 0 && row < SIZE && col >= 0 && col < SIZE && board[row][col] == 0) {
        board[row][col] = step;
        if (step == SIZE * SIZE) {
            show_board(board);
        }
        patrol(board, row - 2, col - 1, step + 1);
        patrol(board, row - 1, col - 2, step + 1);
        patrol(board, row + 1, col - 2, step + 1);
        patrol(board, row + 2, col - 1, step + 1);
        patrol(board, row + 2, col + 1, step + 1);
        patrol(board, row + 1, col + 2, step + 1);
        patrol(board, row - 1, col + 2, step + 1);
        patrol(board, row - 2, col + 1, step + 1);
        board[row][col] = 0;
    }
}

int main() {
    vector<vector<int> > board(SIZE, vector<int>(SIZE, 0));
    patrol(board);
    return 0;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define MAX_NODE_NUN 100
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int *ret = malloc(sizeof(int) * (MAX_NODE_NUN+1));
    *returnSize = 0;
    preorder(root, returnSize, ret);
    return ret;
}

void preorder(struct TreeNode* root, int* retIndex, int *ret) {
    if (root == NULL) {
        return;
    }

    ret[(*retIndex)++] = root->val;
    preorder(root->left, retIndex, ret);
    preorder(root->right, retIndex, ret);
}

void backTracking(int* nums, int numsSize, int* used) {
    if(pathTop == numsSize) {
        copy();
        return;
    }

    int i;
    for(i = 0; i < numsSize; i++) {
        if(used[i])
            continue;
        used[i] = 1;
        path[pathTop++] = nums[i];
        backTracking(nums, numsSize, used);
        //回溯
        pathTop--;
        used[i] = 0;
    }
}

# [1,2,3,4]中取两个数

首次循环开始：
    nums[i]为1，取1后开始递归，
    选取下一个数字，将会取 [2,3,4] （因为1取过之后使用used[i]进行了标记）
第二次循环开始：
    nums[i]为2，取2后开始递归
    但是取2之前需要将递归之前取的1删掉，因为每次只能取一个数，进入递归之后才会取下一个数
...