代码随想录——回溯

组合

77. 组合

思路：回溯

1. 从 1 开始，逐个尝试选择数字，结果是升序序列。
2. 如果当前组合的长度等于 k，将其加入结果。
3. 如果未达到 k，继续递归选择下一个数字。
4. 通过回溯（撤销选择）来尝试其他可能性。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// 回溯函数
void backtrack(int n, int k, int start, int *path, int pathSize, int **result, int *resultSize, int *returnColumnSizes) {
    // 如果当前组合的长度等于 k，将其加入结果
    if (pathSize == k) {
        result[*resultSize] = malloc(sizeof(int) * k);  // 为当前组合分配内存
        memcpy(result[*resultSize], path, sizeof(int) * k);  // 复制当前组合到结果数组
        returnColumnSizes[*resultSize] = k;  // 设置当前组合的大小
        (*resultSize)++;  // 结果数组的索引加 1
        return;
    }
    //剪枝，也可以不加
    if(n-start+1+pathSize<k)return;

    // 从 start 开始尝试选择数字
    for (int i = start; i <= n; i++) {
        path[pathSize] = i;  // 选择当前数字
        backtrack(n, k, i + 1, path, pathSize + 1, result, resultSize, returnColumnSizes);  // 递归选择下一个数字
    }
}

// 主函数：生成所有组合
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    // 计算组合的总数 C(n, k)
    int total = 1;
    for (int i = 1; i <= k; i++) {
        total *= (n - i + 1);
        total /= i;
    }
    *returnSize = total;  // 设置返回的组合总数

    // 分配内存
    int **result = malloc(sizeof(int*) * total);  // 结果数组
    *returnColumnSizes = malloc(sizeof(int) * total);  // 每个组合的大小数组
    int *path = malloc(sizeof(int) * k);  // 当前组合的临时数组

    int resultSize = 0;  // 结果数组的当前索引
    backtrack(n, k, 1, path, 0, result, &resultSize, *returnColumnSizes);  // 调用回溯函数生成所有组合

    // 释放临时数组的内存
    free(path);

    return result;  // 返回结果数组
}

组合总数

216. 组合总和 III

思路：回溯

1. 问题分解：
   • 从 1 到 9 中选择 k 个数，使得它们的和等于 n。
   • 每个数字只能使用一次，且组合中的数字按升序排列。
2. 回溯算法的关键点：
   • 选择数字：从 1 开始，逐个尝试选择数字。
   • 递归：在选择一个数字后，递归选择下一个数字。
   • 剪枝：如果当前组合的和已经超过 n，或者组合的长度已经超过 k，则停止递归（剪枝）。
   • 保存结果：如果当前组合的长度等于 k 且和等于 n，将其加入结果。
3. 实现步骤：
   • 使用一个临时数组 path 存储当前组合。
   • 使用递归函数 dfs 遍历所有可能的组合。
   • 在递归过程中，确保组合中的数字按升序排列，避免重复组合。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// 深度优先搜索（DFS）函数
void dfs(int k, int n, int start, int *returnSize, int *path, int pathsize, int **res, int **returnColumnSizes) {
    // 如果当前组合的长度等于 k 且和为 n，将其加入结果数组
    if (n == 0 && pathsize == k) {
        res[*returnSize] = malloc(sizeof(int) * k);  // 为当前组合分配内存
        memcpy(res[*returnSize], path, sizeof(int) * k);  // 复制当前组合到结果数组
        (*returnColumnSizes)[*returnSize] = k;  // 设置当前组合的大小
        (*returnSize)++;  // 结果数组的索引加 1
        return;
    }

    // 如果当前和已经小于 0 或组合长度超过 k，直接返回
    if (n < 0 || pathsize >= k) return;

    // 从 start 开始尝试选择数字
    for (int i = start; i <= 9; i++) {
        path[pathsize] = i;  // 选择当前数字
        dfs(k, n - i, i + 1, returnSize, path, pathsize + 1, res, returnColumnSizes);  // 递归选择下一个数字
    }
}

// 主函数：生成所有符合条件的组合
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;  // 初始化返回的组合数量为 0

    // 分配内存
    *returnColumnSizes = malloc(sizeof(int) * 512);  // 每个组合的大小数组，最多有 2^9=512 个组合
    int *path = malloc(sizeof(int) * k);  // 当前组合的临时数组
    int **res = malloc(sizeof(int*) * 512);  // 结果数组，最多有 2^9=512 个组合

    // 调用 DFS 函数生成所有组合
    dfs(k, n, 1, returnSize, path, 0, res, returnColumnSizes);

    // 释放临时数组的内存
    free(path);

    return res;  // 返回结果数组
}

电话号码的字母组合

17. 电话号码的字母组合

思路：思路不难，就是用字母替换相应的数字

// 数字到字母的映射
const char *digitToLetters[10] = {
    "",     // 0
    "",     // 1
    "abc",  // 2
    "def",  // 3
    "ghi",  // 4
    "jkl",  // 5
    "mno",  // 6
    "pqrs", // 7
    "tuv",  // 8
    "wxyz"  // 9
};

// 深度优先搜索（DFS）函数
void dfs(char *digits, int *returnSize, char *path, int pathsize, char **res) {
    // 如果当前组合的长度等于 digits 的长度，将其加入结果数组
    if (pathsize == strlen(digits)) {
        res[*returnSize] = malloc(sizeof(char) * (pathsize + 1));  // 为当前组合分配内存
        memcpy(res[*returnSize], path, sizeof(char) * pathsize);   // 复制当前组合到结果数组
        res[*returnSize][pathsize] = '\0';  // 添加字符串结束符
        (*returnSize)++;  // 结果数组的索引加 1
        return;
    }

    // 获取当前数字对应的字母集合
    int digit = digits[pathsize] - '0';  // 将字符转换为数字
    const char *letters = digitToLetters[digit];  // 获取对应的字母集合

    // 遍历当前数字对应的所有字母
    for (int i = 0; i < strlen(letters); i++) {
        path[pathsize] = letters[i];  // 选择当前字母
        dfs(digits, returnSize, path, pathsize + 1, res);  // 递归选择下一个字母
    }
}

// 主函数：生成所有字母组合
char** letterCombinations(char* digits, int* returnSize) {
    int len = strlen(digits);
    *returnSize = 0;  // 初始化返回的组合数量为 0

    // 如果输入为空，直接返回空数组
    if (len == 0) {
        return NULL;
    }

    // 计算所有可能的组合总数
    int total = 1;
    for (int i = 0; i < len; i++) {
        int digit = digits[i] - '0';
        total *= strlen(digitToLetters[digit]);
    }

    // 分配内存
    char **res = malloc(sizeof(char*) * total);  // 结果数组
    char *path = malloc(sizeof(char) * (len + 1));  // 当前组合的临时数组

    // 调用 DFS 函数生成所有组合
    dfs(digits, returnSize, path, 0, res);

    // 释放临时数组的内存
    free(path);

    return res;  // 返回结果数组
}

组合总数

39. 组合总和

思路：与前面组合总数思路差不多，不同点在于本题的数字可以重复选取

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
/**
 * 递归函数：深度优先搜索（DFS）寻找所有组合
 * @param candidates 候选数字数组
 * @param n 候选数组的大小
 * @param start 当前递归的起始索引（避免重复组合）
 * @param target 剩余目标和
 * @param path 当前路径（存储当前组合）
 * @param pathsize 当前路径的大小
 * @param res 结果数组（存储所有有效组合）
 * @param returnSize 当前找到的有效组合数量
 * @param returnColumnSizes 存储每个组合大小的数组
 */
void dfs(int *candidates, int n, int start, int target, int *path, int pathsize, int **res, int *returnSize, int **returnColumnSizes) {
    // 如果剩余目标和为 0，说明当前路径是一个有效组合
    if (target == 0) {
        // 分配内存存储当前组合
        res[*returnSize] = malloc(sizeof(int) * pathsize);
        // 将当前路径复制到结果数组中
        memcpy(res[*returnSize], path, sizeof(int) * pathsize);
        // 记录当前组合的大小
        (*returnColumnSizes)[*returnSize] = pathsize;
        // 有效组合数量加 1
        (*returnSize)++;
        return;
    }
    // 如果剩余目标和为负数，说明当前路径无效，直接返回
    if (target < 0) {
        return;
    }
    // 遍历候选数组，尝试将每个数字加入路径
    for (int i = start; i < n; i++) {
        // 将当前候选数字加入路径
        path[pathsize] = candidates[i];
        // 递归调用，更新剩余目标和及路径大小
        dfs(candidates, n, i, target - candidates[i], path, pathsize + 1, res, returnSize, returnColumnSizes);
    }
    return;
}

/**
 * 主函数：寻找所有组合
 * @param candidates 候选数字数组
 * @param candidatesSize 候选数组的大小
 * @param target 目标和
 * @param returnSize 返回有效组合的数量
 * @param returnColumnSizes 返回每个组合的大小
 * @return 返回所有有效组合的数组
 */
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    // 初始化有效组合数量为 0
    *returnSize = 0;
    // 为存储组合大小的数组分配内存（假设最多有 150 种组合）
    *returnColumnSizes = malloc(sizeof(int) * 150);
    // 为当前路径分配内存（假设路径大小最多为 30）
    int *path = malloc(sizeof(int) * 30);
    // 为结果数组分配内存（假设最多有 150 种组合）
    int **res = malloc(sizeof(int*) * 150);
    // 调用 DFS 函数，开始寻找组合
    dfs(candidates, candidatesSize, 0, target, path, 0, res, returnSize, returnColumnSizes);
    // 释放临时路径数组的内存
    free(path);
    // 返回结果数组
    return res;
}

组合总数Ⅱ

40. 组合总和 II

思路：

1. 排序：
   • 对 candidates 排序，方便去重和剪枝。
2. 回溯算法：
   • 通过递归遍历所有可能的组合。
   • 在每一层递归中，从当前索引开始遍历候选数组。
3. 去重：
   • 如果当前数字与前一个数字相同，且不是当前递归层的第一个数字，则跳过。
4. 剪枝：
   • 如果当前数字大于剩余目标和，直接跳过后续数字。
5. 终止条件：
   • 如果剩余目标和为 0，保存当前组合。
   • 如果剩余目标和为负数，直接返回。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
/**
 * 递归函数：深度优先搜索（DFS）寻找所有组合
 * @param candidates 候选数字数组
 * @param n 候选数组的大小
 * @param start 当前递归的起始索引（避免重复组合）
 * @param target 剩余目标和
 * @param path 当前路径（存储当前组合）
 * @param pathsize 当前路径的大小
 * @param res 结果数组（存储所有有效组合）
 * @param returnSize 当前找到的有效组合数量
 * @param returnColumnSizes 存储每个组合大小的数组
 */
void dfs(int *candidates, int n, int start, int target, int *path, int pathsize, int **res, int *returnSize, int **returnColumnSizes) {
    // 如果剩余目标和为 0，说明当前路径是一个有效组合
    if (target == 0) {
        // 分配内存存储当前组合
        res[*returnSize] = malloc(sizeof(int) * pathsize);
        // 将当前路径复制到结果数组中
        memcpy(res[*returnSize], path, sizeof(int) * pathsize);
        // 记录当前组合的大小
        (*returnColumnSizes)[*returnSize] = pathsize;
        // 有效组合数量加 1
        (*returnSize)++;
        return;
    }
    // 如果剩余目标和为负数，说明当前路径无效，直接返回
    if (target < 0) {
        return;
    }
    // 遍历候选数组，尝试将每个数字加入路径
    for (int i = start; i < n; i++) {
        // 如果当前数字与前一个数字相同，且不是递归的起始位置，跳过（去重）
        if(i>start&&candidates[i-1]==candidates[i])continue;
        // 将当前候选数字加入路径
        path[pathsize] = candidates[i];
        // 递归调用，更新剩余目标和及路径大小
        dfs(candidates, n, i+1, target - candidates[i], path, pathsize + 1, res, returnSize, returnColumnSizes);
    }
    return;
}

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
/**
 * 主函数：寻找所有组合
 * @param candidates 候选数字数组
 * @param candidatesSize 候选数组的大小
 * @param target 目标和
 * @param returnSize 返回有效组合的数量
 * @param returnColumnSizes 返回每个组合的大小
 * @return 返回所有有效组合的数组
 */
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    // 初始化有效组合数量为 0
    *returnSize = 0;
    // 为存储组合大小的数组分配内存（假设最多有 150 种组合）
    *returnColumnSizes = malloc(sizeof(int) * 150);
    // 为当前路径分配内存（假设路径大小最多为 30）
    int *path = malloc(sizeof(int) * 30);
    // 为结果数组分配内存（假设最多有 150 种组合）
    int **res = malloc(sizeof(int*) * 150);
    qsort(candidates,candidatesSize,sizeof(int),cmp);
    // 调用 DFS 函数，开始寻找组合
    dfs(candidates, candidatesSize, 0, target, path, 0, res, returnSize, returnColumnSizes);
    // 释放临时路径数组的内存
    free(path);
    // 返回结果数组
    return res;
}

分割回文串

131. 分割回文串

思路：dfs+回溯

• 使用回溯算法遍历所有可能的分割方式。
• 在每一层递归中，尝试从当前位置开始分割出一个回文子串。
• 如果当前子串是回文，则将其加入路径，并递归处理剩余部分。
• 如果当前分割位置到达字符串末尾，说明找到一种有效的分割方案，将其保存到结果中。

// 判断子串 s[left...right] 是否是回文
bool ishuiwen(char *s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return false; // 如果字符不相等，不是回文
        left++;
        right--;
    }
    return true; // 是回文
}

// 回溯函数
void dfs(char *s, int start, int len, char **path, int pathSize, char ***res, int *returnSize, int **returnColumnSizes) {
    // 如果当前分割位置到达字符串末尾，保存当前分割方案
    if (start == len) {
        res[*returnSize] = malloc(sizeof(char*) * pathSize); // 分配内存存储当前分割方案
        for (int i = 0; i < pathSize; i++) {
            res[*returnSize][i] = malloc(strlen(path[i]) + 1); // 分配内存并复制字符串
            strcpy(res[*returnSize][i], path[i]);
        }
        (*returnColumnSizes)[*returnSize] = pathSize; // 记录当前分割方案的大小
        (*returnSize)++; // 有效分割方案数量加 1
        return;
    }
    // 尝试从当前位置开始分割
    for (int i = start; i < len; i++) {
        // 如果子串 s[start...i] 是回文，则继续递归
        if (ishuiwen(s, start, i)) {
            // 将当前回文子串加入路径
            path[pathSize] = malloc(i - start + 2); // 分配内存并复制字符串
            strncpy(path[pathSize], s + start, i - start + 1);
            path[pathSize][i - start + 1] = '\0'; // 添加字符串结束符
            // 递归处理剩余部分
            dfs(s, i + 1, len, path, pathSize + 1, res, returnSize, returnColumnSizes);
            // 回溯，移除当前子串
            free(path[pathSize]);
        }
    }
}

// 主函数
char ***partition(char *s, int *returnSize, int **returnColumnSizes) {
    int len = strlen(s);
    // 初始化结果
    *returnSize = 0; // 有效分割方案数量初始化为 0
    *returnColumnSizes = malloc(sizeof(int) * 100000); // 假设最多有 100000 种分割方案
    char ***res = malloc(sizeof(char**) * 100000); // 假设最多有 100000 种分割方案
    char **path = malloc(sizeof(char*) * len); // 当前路径
    // 调用回溯函数
    dfs(s, 0, len, path, 0, res, returnSize, returnColumnSizes);
    // 释放临时路径数组
    free(path);
    return res; // 返回所有有效的分割方案
}

复原IP地址

93. 复原 IP 地址

思路：dfs，回溯，和前面都差不多。

回溯算法

• 使用回溯算法尝试所有可能的分割方案。
• 每次尝试将字符串分割成 4 个部分，每个部分必须满足 IP 段的条件。

有效 IP 段的判断

• 每个 IP 段必须满足以下条件：
  1. 值在 0 到 255 之间。
  2. 不能有前导零（除非是 0 本身）。
  3. 必须是数字字符。

递归终止条件

• 如果已经分成 4 段且字符串被完全使用，当前分割方案是一个有效的 IP 地址，将其保存到结果中。

剪枝优化

• 如果当前分割的段数已经超过 4 段，直接返回。
• 如果剩余字符串的长度不足以分成剩余部分，直接返回。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

// 判断子串 s[left...right] 是否是有效的 IP 段
bool isValidSegment(char *s, int left, int right) {
    if (right == left) return true; // 单个字符是有效的
    if (left > right || s[left] == '0') return false; // 前导零无效（除非是 "0" 本身）
    int sum = 0;
    for (int i = left; i <= right; i++) {
        if (s[i] < '0' || s[i] > '9') return false; // 非数字字符无效
        sum = sum * 10 + (s[i] - '0'); // 计算子串的数值
        if (sum > 255) return false; // 超过 255 无效
    }
    return true; // 子串有效
}

// 回溯函数
void dfs(char *s, int start, int len, char **path, int pathSize, char **res, int *returnSize) {
    // 如果已经分成 4 段且字符串被完全使用
    if (pathSize == 4 && start == len) {
        // 分配内存存储当前 IP 地址
        res[*returnSize] = malloc(sizeof(char) * (len + 4)); // len + 4 是为了容纳 3 个点号和结束符
        int index = 0;
        // 将每一段拼接到结果中
        for (int i = 0; i < 4; i++) {
            strcpy(res[*returnSize] + index, path[i]); // 复制当前段
            index += strlen(path[i]); // 移动索引
            if (i < 3) {
                res[*returnSize][index++] = '.'; // 添加点号
            }
        }
        res[(*returnSize)++][index] = '\0'; // 添加字符串结束符，并增加有效 IP 地址数量
        return;
    }

    // 如果已经分成 4 段但字符串未完全使用，直接返回
    if (pathSize == 4) return;

    // 尝试从当前位置开始分割
    for (int i = start; i < len && i < start + 3; i++) { // 每段最多 3 位
        if (isValidSegment(s, start, i)) { // 如果子串 s[start...i] 是有效的 IP 段
            // 分配内存并复制当前段
            path[pathSize] = malloc(sizeof(char) * (i - start + 2)); // i - start + 1 是子串长度，+1 用于结束符
            strncpy(path[pathSize], s + start, i - start + 1); // 复制子串
            path[pathSize][i - start + 1] = '\0'; // 添加字符串结束符
            // 递归处理剩余部分
            dfs(s, i + 1, len, path, pathSize + 1, res, returnSize);
            // 回溯，释放当前段内存
            free(path[pathSize]);
        }
    }
}

// 主函数
char **restoreIpAddresses(char *s, int *returnSize) {
    int len = strlen(s);
    *returnSize = 0; // 初始化有效 IP 地址数量为 0
    char **res = malloc(sizeof(char*) * 1000); // 假设最多有 1000 种有效 IP 地址
    char *path[4]; // 当前路径，存储 4 段 IP 地址

    // 调用回溯函数
    dfs(s, 0, len, path, 0, res, returnSize);

    return res; // 返回所有有效的 IP 地址
}

子集

78. 子集

思路：dfs+回溯

与上面几题的区别在于：本题每次递归的状态（path）都是我们需要的答案，因此没有if(path==numsSize)这个终止条件，其他都一样。

具体见代码：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// 回溯函数
void dfs(int *nums, int numsSize, int start, int *path, int pathSize, int **res, int *returnSize, int **returnColumnSizes) {
    // 将当前路径保存到结果中
    res[*returnSize] = malloc(sizeof(int) * pathSize); // 分配内存存储当前子集
    memcpy(res[*returnSize], path, sizeof(int) * pathSize); // 复制当前路径到结果中
    (*returnColumnSizes)[*returnSize] = pathSize; // 记录当前子集的大小
    (*returnSize)++; // 增加结果的数量

    // 遍历数组，尝试选择或不选择当前元素
    for (int i = start; i < numsSize; i++) {
        // 选择当前元素
        path[pathSize] = nums[i]; // 将当前元素加入路径
        // 递归处理剩余元素
        dfs(nums, numsSize, i + 1, path, pathSize + 1, res, returnSize, returnColumnSizes);
        // 注意：这里不需要显式回溯，因为 pathSize 在递归调用时会自动恢复
    }
    return;
}

// 主函数
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 初始化结果数组
    int **res = malloc(sizeof(int*) * 1024); // 假设最多有 1024 个子集
    int *path = malloc(sizeof(int) * 10); // 假设路径长度最多为 10
    *returnSize = 0; // 初始化结果数量为 0
    *returnColumnSizes = malloc(sizeof(int) * 1024); // 假设最多有 1024 个子集

    // 调用回溯函数
    dfs(nums, numsSize, 0, path, 0, res, returnSize, returnColumnSizes);

    // 返回所有子集
    return res;
}

子集Ⅱ

90. 子集 II

思路：如果上题**78. 子集懂了，那么这题只需要注意去重就行，而去重的方法在40. 组合总和 II**也已经实现了。基于上题上题的基础，只需要加上排序和去重就可以了。

1. 排序：
   • 使用 qsort 对输入数组 nums 进行排序，以便跳过重复元素。
2. 回溯函数 dfs：
   • 将当前路径 path 保存到结果 res 中。
   • 遍历数组，选择或不选择当前元素。
   • 如果当前元素与前一个元素相同且不是起始位置，则跳过（避免重复子集）。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
// 回溯函数
void dfs(int *nums, int numsSize, int start, int *path, int pathSize, int **res, int *returnSize, int **returnColumnSizes) {
    // 将当前路径保存到结果中
    res[*returnSize] = malloc(sizeof(int) * pathSize); // 分配内存存储当前子集
    memcpy(res[*returnSize], path, sizeof(int) * pathSize); // 复制当前路径到结果中
    (*returnColumnSizes)[*returnSize] = pathSize; // 记录当前子集的大小
    (*returnSize)++; // 增加结果的数量

    // 遍历数组，尝试选择或不选择当前元素
    for (int i = start; i < numsSize; i++) {
        if(i>start&&nums[i]==nums[i-1])continue;
        // 选择当前元素
        path[pathSize] = nums[i]; // 将当前元素加入路径
        // 递归处理剩余元素
        dfs(nums, numsSize, i + 1, path, pathSize + 1, res, returnSize, returnColumnSizes);
        // 注意：这里不需要显式回溯，因为 pathSize 在递归调用时会自动恢复
    }
    return;
}
int cmp(const void* a,const void* b){
    return *(int*)a-*(int*)b;
}
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums,numsSize,sizeof(int),cmp);
    // 初始化结果数组
    int **res = malloc(sizeof(int*) * 1024); // 假设最多有 1024 个子集
    int *path = malloc(sizeof(int) * 10); // 假设路径长度最多为 10
    *returnSize = 0; // 初始化结果数量为 0
    *returnColumnSizes = malloc(sizeof(int) * 1024); // 假设最多有 1024 个子集

    // 调用回溯函数
    dfs(nums, numsSize, 0, path, 0, res, returnSize, returnColumnSizes);

    // 返回所有子集
    return res;
}

非递减子序列

491. 非递减子序列

思路：dfs+回溯获取所有非递减子序列，选取pathSize>=2的序列。

这里与之前不同的点在于去重的逻辑，前面的去重是在排序之后的数组进行，而本题，而本题并不能排序。采取的是用哈希表记录某数是否已经使用。
下面是AI生成的去重总结，我觉得不错：

去重的核心思想是：在同一递归层级中，如果当前数字已经使用过，则跳过该数字。

去重的实现方法

方法 1：排序 + 跳过重复元素

• 如果输入数组是有序的，可以直接跳过重复元素。
• 例如，在 nums = [4, 6, 7, 7] 中，当遍历到第二个 7 时，如果发现它和前一个元素相同，则跳过。

代码示例：

if (i > start && nums[i] == nums[i - 1]) continue;

• 作用：
  • 如果当前数字 nums[i] 和前一个数字 nums[i - 1] 相同，并且 i > start，则跳过该数字。
  • 这样可以避免在同一层级中重复使用相同的数字。
• 局限性：
  • 这种去重方法依赖于输入数组的有序性。如果输入数组是无序的，这种逻辑可能无法完全去重。

方法 2：使用哈希表或数组记录已使用的数字

• 在每一层递归中，使用一个哈希表或数组记录当前层级已经使用过的数字。
• 如果当前数字已经存在于哈希表中，则跳过该数字。

代码：

为了更通用地处理去重问题，可以在每一层递归中使用一个数组（或哈希表）记录已经使用过的数字。以下是改进的去重逻辑：

int used[201] = {0};  // 用于去重，记录当前递归层中已经使用过的数字
for (int i = start; i < numsSize; i++) {
    // 如果当前数字已经使用过，则跳过
    if (used[nums[i] + 100]) {
        continue;
    }
    used[nums[i] + 100] = 1;  // 标记当前数字已使用
    // 其他逻辑...
}

• used 数组的作用：
  • used 数组用于记录当前递归层级中已经使用过的数字。
  • 数组大小为 201，是因为题目中数字的范围是 [-100, 100]，所以将数字 nums[i] 映射到 nums[i] + 100，确保索引非负。
• 优点：
  • 不依赖于输入数组的有序性。
  • 可以完全避免重复子序列。

去重的完整示例

假设输入数组为 nums = [4, 6, 7, 7]，去重的过程如下：

1. 第一层递归：

   • 选择 4，生成子序列 [4]。
   • 选择 6，生成子序列 [6]。
   • 选择 7，生成子序列 [7]。
   • 再次选择 7，发现 7 已经使用过，跳过。

2. 第二层递归：

   • 从 4 开始：
     • 选择 6，生成子序列 [4, 6]。
     • 选择 7，生成子序列 [4, 7]。
     • 再次选择 7，发现 7 已经使用过，跳过。
   • 从 6 开始：
     • 选择 7，生成子序列 [6, 7]。
     • 再次选择 7，发现 7 已经使用过，跳过。
   • 从 7 开始：
     • 选择 7，生成子序列 [7, 7]。

3. 结果：

   • 最终生成的子序列为：

     [4, 6]
     [4, 7]
     [6, 7]
     [7, 7]
     

总结

去重的核心思路是：在同一递归层级中，避免重复使用相同的数字。可以通过以下方法实现：

1. 排序 + 跳过重复元素：适用于有序数组。
2. 哈希表或数组记录已使用的数字：适用于任意数组，更通用。

本题代码

/**
 * DFS 函数：递归生成所有非递减子序列
 * @param nums: 输入数组
 * @param numsSize: 输入数组的大小
 * @param start: 当前递归的起始位置
 * @param path: 当前生成的子序列
 * @param pathSize: 当前子序列的长度
 * @param res: 存储所有符合条件的子序列
 * @param returnSize: 当前找到的子序列的数量
 * @param returnColumnSizes: 存储每个子序列的长度的数组
 */
void dfs(int *nums, int numsSize, int start, int *path, int pathSize, int **res, int *returnSize, int **returnColumnSizes) {
    // 如果当前子序列的长度大于等于 2，将其加入结果集
    if (pathSize >= 2) {
        res[*returnSize] = malloc(sizeof(int) * pathSize);  // 为当前子序列分配内存
        memcpy(res[*returnSize], path, sizeof(int) * pathSize);  // 将当前子序列复制到结果集中
        (*returnColumnSizes)[*returnSize] = pathSize;  // 记录当前子序列的长度
        (*returnSize)++;  // 增加结果集的子序列数量
    }

    int used[201] = {0};  // 用于去重，记录当前递归层中已经使用过的数字
    for (int i = start; i < numsSize; i++) {
        // 如果当前子序列不为空，且当前数字小于子序列的最后一个数字，则跳过（确保子序列是非递减的）
        if (pathSize > 0 && nums[i] < path[pathSize - 1]) {
            continue;
        }
        // 如果当前数字在当前递归层中已经使用过，则跳过（避免重复子序列）
        if (used[nums[i] + 100]) {
            continue;
        }
        used[nums[i] + 100] = 1;  // 标记当前数字已使用
        path[pathSize] = nums[i];  // 将当前数字加入子序列
        dfs(nums, numsSize, i + 1, path, pathSize + 1, res, returnSize, returnColumnSizes);  // 递归生成子序列
    }
}

/**
 * 主函数：找到所有非递减子序列
 * @param nums: 输入数组
 * @param numsSize: 输入数组的大小
 * @param returnSize: 用于返回找到的子序列的数量
 * @param returnColumnSizes: 用于返回每个子序列的长度的数组
 * @return: 返回一个二维数组，包含所有非递减子序列
 */
int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int **res = malloc(sizeof(int*) * 40000);  // 分配结果数组的内存
    *returnSize = 0;  // 初始化子序列数量为 0
    *returnColumnSizes = malloc(sizeof(int) * 40000);  // 分配子序列长度数组的内存
    int *path = malloc(sizeof(int) * numsSize);  // 分配路径数组的内存
    dfs(nums, numsSize, 0, path, 0, res, returnSize, returnColumnSizes);  // 调用 DFS 函数生成子序列
    free(path);  // 释放路径数组的内存
    return res;  // 返回结果数组
}

全排列

46. 全排列

思路：dfs+回溯

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void dfs(int *nums, int numsSize, bool *used, int *path, int pathSize, int **res, int *returnSize, int **returnColumnSizes) {
    // 如果路径长度等于数组长度，说明找到了一个完整的排列
    if (pathSize == numsSize) {
        // 为结果数组分配内存
        res[*returnSize] = malloc(sizeof(int) * pathSize);
        // 将当前路径复制到结果数组中
        memcpy(res[*returnSize], path, sizeof(int) * pathSize);
        // 更新返回列大小数组
        (*returnColumnSizes)[*returnSize] = pathSize;
        // 增加返回大小
        (*returnSize)++;
        return;
    }
    // 遍历数组中的每个数字
    for (int i = 0; i < numsSize; i++) {
        // 如果当前数字已经被使用过，则跳过
        if (used[i]) continue;
        // 将当前数字加入路径
        path[pathSize] = nums[i];
        // 标记当前数字为已使用
        used[i] = 1;
        // 递归调用dfs函数，继续寻找下一个数字
        dfs(nums, numsSize, used, path, pathSize + 1, res, returnSize, returnColumnSizes);
        // 回溯，将当前数字标记为未使用
        used[i] = 0;
    }
    return;
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 为结果数组分配内存，假设最大排列数为720（6!）
    int **res = malloc(sizeof(int*) * 720);
    // 为路径数组分配内存，假设最大路径长度为6
    int *path = malloc(sizeof(int) * 6);
    // 为返回列大小数组分配内存
    *returnColumnSizes = malloc(sizeof(int) * 720);
    // 初始化返回大小为0
    *returnSize = 0;
    // 初始化已使用数组
    bool used[25] = {0};
    // 调用dfs函数，开始深度优先搜索
    dfs(nums, numsSize, used, path, 0, res, returnSize, returnColumnSizes);
    // 返回结果数组
    return res;
}

全排列Ⅱ

47. 全排列 II

思路：dfs+回溯+排序+去重

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// 深度优先搜索函数，用于生成排列
void dfs(int *nums, int numsSize, int *path, int pathSize, int *used, int **res, int *returnSize, int **returnColumnSizes) {
    // 如果路径长度等于数组长度，说明找到了一个完整的排列
    if (pathSize == numsSize) {
        // 为结果数组分配内存
        res[*returnSize] = malloc(sizeof(int) * pathSize);
        // 将当前路径复制到结果数组中
        memcpy(res[*returnSize], path, sizeof(int) * pathSize);
        // 更新返回列大小数组
        (*returnColumnSizes)[*returnSize] = pathSize;
        // 增加返回大小
        (*returnSize)++;
        return;
    }
    // 遍历输入数组中的每个元素
    for (int i = 0; i < numsSize; i++) {
        // 如果当前元素的剩余使用次数为0，跳过
        if (used[nums[i] + 10] == 0) continue;
        // 如果当前元素与前一个元素相同，且前一个元素未被使用，跳过
        if (i > 0 && nums[i] == nums[i - 1] && used[nums[i - 1] + 10] > 0) continue;
        // 减少当前元素的剩余使用次数
        used[nums[i] + 10]--;
        // 将当前元素加入路径
        path[pathSize] = nums[i];
        // 递归调用dfs函数，继续寻找下一个元素
        dfs(nums, numsSize, path, pathSize + 1, used, res, returnSize, returnColumnSizes);
        // 回溯，增加当前元素的剩余使用次数
        used[nums[i] + 10]++;
    }
}

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

// 主函数，生成所有不重复的排列
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 对输入数组进行排序
    qsort(nums, numsSize, sizeof(int), cmp);
    // 计算可能的排列总数
    int total = 1;
    for (int i = 2; i <= numsSize; i++) total *= i;
    // 为结果数组分配内存
    int **res = malloc(sizeof(int *) * total);
    // 为路径数组分配内存
    int *path = malloc(sizeof(int) * numsSize);
    // 初始化计数数组
    int used[25] = {0};
    // 统计每个数字的出现次数
    for (int i = 0; i < numsSize; i++) {
        used[nums[i] + 10]++;
    }
    // 初始化返回大小
    *returnSize = 0;
    // 为返回列大小数组分配内存
    *returnColumnSizes = malloc(sizeof(int) * total);
    // 调用dfs函数，开始深度优先搜索
    dfs(nums, numsSize, path, 0, used, res, returnSize, returnColumnSizes);
    // 返回结果数组
    return res;
}

重新安排行程

332. 重新安排行程

题目描述

本题第一个挑战就是读懂题。。。下面是题目大意：

给定一个机票的字符串二维数组 tickets，其中 tickets[i] = [fromi, toi] 表示一张从 fromi 飞往 toi 的机票。要求重新构建行程，使得所有的机票都被使用一次且仅使用一次。行程必须从 JFK 开始，并且如果有多个有效的行程，返回字典序最小的那个。

思路

1. 构建邻接表：将每个机场的邻接机场按字典序逆序排列，以便在DFS时优先访问字典序较小的机场。
2. 深度优先搜索（DFS）：从JFK出发，递归访问每个机场的邻接机场，直到无法继续为止。每次访问后移除该边，确保每条边只使用一次。
3. 结果处理：DFS遍历是后序遍历，因此结果需要反转才能得到正确的行程顺序

代码逻辑

1. 机场ID映射：

   • 使用 str2id 将机场字符串（如 “JFK”）转换为唯一的整数ID。
   • 使用 id2str 将ID映射回字符串，方便最终结果的输出。

2. 机票排序：

   • 将机票转换为 {起点ID, 终点ID} 的形式。
   • 使用 qsort 对机票按起点和终点降序排序，确保DFS优先访问字典序较小的机场。

3. 邻接表构建：

   • 使用 vec 数组存储每个机场的邻接机场。
   • vec_len 记录每个机场的邻接机场数量。

4. DFS遍历：

   • 从 “JFK” 开始递归遍历图。
   • 每次访问一个机场时，将其邻接机场按顺序加入栈中。
   • 最终栈中存储的是后序遍历的结果。

5. 结果处理：

   • 将栈中的结果反转，得到正确的行程顺序。
   • 返回结果数组。

代码1：官方题解

// 全局变量：用于将机场ID映射回字符串
char* id2str[26 * 26 * 26];

// 将机场字符串转换为唯一的ID
int str2id(char* a) {
    int ret = 0;
    for (int i = 0; i < 3; i++) {
        ret = ret * 26 + a[i] - 'A'; // 将字符转换为0-25的数字，并计算唯一ID
    }
    return ret;
}

// 比较函数：用于对机票进行排序
int cmp(const void* _a, const void* _b) {
    int **a = (int**)_a, **b = (int**)_b;
    // 先按起点排序，起点相同则按终点排序（降序）
    return (*b)[0] - (*a)[0] ? (*b)[0] - (*a)[0] : (*b)[1] - (*a)[1];
}

// 邻接表：存储每个机场的邻接机场
int* vec[26 * 26 * 26];
int vec_len[26 * 26 * 26]; // 每个机场的邻接机场数量

// 栈：用于存储DFS遍历的结果
int* stk;
int stk_len; // 栈的长度

// DFS函数：递归遍历图
void dfs(int curr) {
    // 遍历当前机场的所有邻接机场
    while (vec_len[curr] > 0) {
        int tmp = vec[curr][--vec_len[curr]]; // 取出最后一个邻接机场
        dfs(tmp); // 递归访问
    }
    // 将当前机场加入栈中（后序遍历）
    stk[stk_len++] = curr;
}

// 主函数：重新安排行程
char** findItinerary(char*** tickets, int ticketsSize, int* ticketsColSize, int* returnSize) {
    // 初始化邻接表的长度
    memset(vec_len, 0, sizeof(vec_len));
    // 初始化栈
    stk = malloc(sizeof(int) * (ticketsSize + 1));
    stk_len = 0;

    // 将机票转换为ID形式，方便处理
    int* tickets_tmp[ticketsSize];
    for (int i = 0; i < ticketsSize; i++) {
        tickets_tmp[i] = (int*)malloc(sizeof(int) * 2);
        tickets_tmp[i][0] = str2id(tickets[i][0]); // 起点ID
        tickets_tmp[i][1] = str2id(tickets[i][1]); // 终点ID
        // 将ID映射回字符串
        id2str[tickets_tmp[i][0]] = tickets[i][0];
        id2str[tickets_tmp[i][1]] = tickets[i][1];
    }
    // 对机票进行排序（按起点和终点降序）
    qsort(tickets_tmp, ticketsSize, sizeof(int*), cmp);

    // 构建邻接表
    int add = 0;
    while (add < ticketsSize) {
        int adds = add + 1, start = tickets_tmp[add][0];
        // 找到所有起点相同的机票
        while (adds < ticketsSize && start == tickets_tmp[adds][0]) {
            adds++;
        }
        // 设置邻接表的长度
        vec_len[start] = adds - add;
        // 分配内存并填充邻接表
        vec[start] = malloc(sizeof(int) * vec_len[start]);
        for (int i = add; i < adds; i++) {
            vec[start][i - add] = tickets_tmp[i][1]; // 添加邻接机场
        }
        add = adds; // 移动到下一个起点
    }

    // 从JFK开始DFS遍历
    dfs(str2id("JFK"));

    // 设置返回结果的长度
    *returnSize = ticketsSize + 1;
    // 分配内存并填充结果
    char** ret = malloc(sizeof(char*) * (ticketsSize + 1));
    for (int i = 0; i <= ticketsSize; i++) {
        ret[ticketsSize - i] = id2str[stk[i]]; // 反转栈中的结果
    }
    return ret;
}

代码2：deepseek r1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义邻接表节点结构体
typedef struct {
    char src[4];         // 源机场（如 "JFK"）
    char **dests;        // 目标机场列表（邻接表）
    int dests_size;      // 目标机场数量
} AdjEntry;

// 比较函数：用于对邻接表中的目标机场按字典序降序排列
int compare(const void *a, const void *b) {
    return strcmp(*(char **)b, *(char **)a); // 降序排列
}

// DFS函数：递归遍历图
void dfs(char *current, AdjEntry *adjList, int adjSize, char **result, int *result_idx) {
    // 查找当前机场在邻接表中的位置
    int found = -1;
    for (int i = 0; i < adjSize; i++) {
        if (strcmp(adjList[i].src, current) == 0) {
            found = i;
            break;
        }
    }
    // 如果当前机场没有邻接机场，直接加入结果
    if (found == -1) {
        result[*result_idx] = malloc(4 * sizeof(char));
        strcpy(result[*result_idx], current);
        (*result_idx)++;
        return;
    }
    // 遍历当前机场的所有邻接机场
    while (adjList[found].dests_size > 0) {
        // 取出最后一个邻接机场（字典序最小）
        char *next = adjList[found].dests[adjList[found].dests_size - 1];
        adjList[found].dests_size--; // 移除该机票
        dfs(next, adjList, adjSize, result, result_idx); // 递归访问
    }
    // 将当前机场加入结果（后序遍历）
    result[*result_idx] = malloc(4 * sizeof(char));
    strcpy(result[*result_idx], current);
    (*result_idx)++;
}

// 主函数：重新安排行程
char **findItinerary(char ***tickets, int ticketsSize, int *ticketsColSize, int *returnSize) {
    // 初始化邻接表
    AdjEntry *adjList = NULL;
    int adjSize = 0;

    // 构建邻接表
    for (int i = 0; i < ticketsSize; i++) {
        char *src = tickets[i][0]; // 源机场
        char *dst = tickets[i][1]; // 目标机场
        int found = -1;
        // 查找源机场是否已经在邻接表中
        for (int j = 0; j < adjSize; j++) {
            if (strcmp(adjList[j].src, src) == 0) {
                found = j;
                break;
            }
        }
        // 如果源机场不在邻接表中，添加新条目
        if (found == -1) {
            adjSize++;
            adjList = realloc(adjList, adjSize * sizeof(AdjEntry));
            strcpy(adjList[adjSize - 1].src, src);
            adjList[adjSize - 1].dests = NULL;
            adjList[adjSize - 1].dests_size = 0;
            found = adjSize - 1;
        }
        // 添加目标机场到邻接表
        adjList[found].dests_size++;
        adjList[found].dests = realloc(adjList[found].dests, adjList[found].dests_size * sizeof(char *));
        adjList[found].dests[adjList[found].dests_size - 1] = dst;
    }

    // 对每个机场的邻接表按字典序降序排序
    for (int i = 0; i < adjSize; i++) {
        qsort(adjList[i].dests, adjList[i].dests_size, sizeof(char *), compare);
    }

    // 准备结果数组
    char **result = malloc((ticketsSize + 1) * sizeof(char *));
    int result_idx = 0;

    // 从 JFK 开始执行 DFS
    dfs("JFK", adjList, adjSize, result, &result_idx);

    // 反转结果数组（DFS是后序遍历，需要反转）
    for (int i = 0; i < result_idx / 2; i++) {
        char *temp = result[i];
        result[i] = result[result_idx - 1 - i];
        result[result_idx - 1 - i] = temp;
    }

    // 设置返回结果的长度
    *returnSize = result_idx;

    // 释放邻接表内存
    for (int i = 0; i < adjSize; i++) {
        free(adjList[i].dests);
    }
    free(adjList);

    return result;
}

N皇后

51. N 皇后

思路：回溯，dfs，剪枝

1. 回溯法：
   • 使用深度优先搜索（DFS）枚举所有可能的解。
   • 逐行放置皇后，并在放置时检查是否与之前放置的皇后冲突。
   • 如果冲突，则回溯并尝试其他位置。
2. 冲突检查：
   • 列冲突：检查当前列是否已经有皇后。
   • 对角线冲突：检查当前位置的左上方和右上方对角线是否已经有皇后

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * DFS函数：递归解决N皇后问题
 * @param n 棋盘大小
 * @param path 当前路径（棋盘状态）
 * @param pathSize 当前路径长度（已放置的皇后数量）
 * @param res 结果数组
 * @param returnSize 结果数量
 * @param returnColumnSizes 每个解的大小
 */
void dfs(int n, char **path, int pathSize, char ***res, int *returnSize, int **returnColumnSizes) {
    // 如果当前路径长度等于n，说明找到一个解
    if (pathSize == n) {
        // 分配内存存储当前解
        res[*returnSize] = malloc(sizeof(char *) * n);
        for (int i = 0; i < n; i++) {
            res[*returnSize][i] = malloc(sizeof(char) * (n + 1)); // 每行长度为n+1（包括'\0'）
            for (int j = 0; j < n; j++) {
                res[*returnSize][i][j] = path[i][j]; // 复制当前行的内容
            }
            res[*returnSize][i][n] = '\0'; // 字符串结束符
        }
        (*returnColumnSizes)[*returnSize] = n; // 设置当前解的大小
        (*returnSize)++; // 解的数量加1
        return;
    }

    // 尝试在当前行的每一列放置皇后
    for (int i = 0; i < n; i++) {
        int flag = 0; // 冲突标志

        // 检查当前列是否冲突
        for (int j = 0; j < pathSize; j++) {
            if (path[j][i] == 'Q') {
                flag = 1;
                break;
            }
        }
        if (flag) continue; // 如果冲突，跳过

        // 检查右上方对角线是否冲突
        int h = pathSize - 1, r = i + 1;
        while (h >= 0 && r < n) {
            if (path[h][r] == 'Q') {
                flag = 1;
                break;
            }
            h--;
            r++;
        }
        if (flag) continue; // 如果冲突，跳过

        // 检查左上方对角线是否冲突
        h = pathSize - 1, r = i - 1;
        while (h >= 0 && r >= 0) {
            if (path[h][r] == 'Q') {
                flag = 1;
                break;
            }
            h--;
            r--;
        }
        if (flag) continue; // 如果冲突，跳过

        // 在当前行放置皇后
        path[pathSize] = malloc(sizeof(char) * (n + 1));
        for (int j = 0; j < n; j++) {
            path[pathSize][j] = (j == i) ? 'Q' : '.'; // 放置皇后或空位
        }
        path[pathSize][n] = '\0'; // 字符串结束符

        // 递归处理下一行
        dfs(n, path, pathSize + 1, res, returnSize, returnColumnSizes);

        // 回溯：释放当前行的内存
        free(path[pathSize]);
    }
}

/**
 * 主函数：解决N皇后问题
 * @param n 棋盘大小
 * @param returnSize 返回解的数量
 * @param returnColumnSizes 返回每个解的大小
 * @return 所有解的数组
 */
char ***solveNQueens(int n, int *returnSize, int **returnColumnSizes) {
    // 初始化结果数组
    char ***res = malloc(sizeof(char **) * 1000); // 假设最多1000个解
    *returnSize = 0; // 解的数量初始化为0
    *returnColumnSizes = malloc(sizeof(int) * 1000); // 每个解的大小

    // 初始化路径数组
    char **path = malloc(sizeof(char *) * n); // 路径数组，存储当前棋盘状态
    for (int i = 0; i < n; i++) {
        path[i] = malloc(sizeof(char) * (n + 1)); // 每行长度为n+1（包括'\0'）
        memset(path[i], '.', n); // 初始化为空位
        path[i][n] = '\0'; // 字符串结束符
    }

    // 调用DFS函数
    dfs(n, path, 0, res, returnSize, returnColumnSizes);

    // 释放路径数组的内存
    for (int i = 0; i < n; i++) {
        free(path[i]);
    }
    free(path);

    return res;
}

解数独

37. 解数独

思路：dfs

对于空数（为.）的地方，依次尝试填充1到9，只要找到一种正确答案就返回。dfs可以返回bool型

#include <stdbool.h>
#include <stdio.h>

// 检查当前数字是否合法
bool isvaild(char **board, int col, int row, char x) {
    // 检查行
    for (int i = 0; i < 9; i++) {
        if (board[col][i] == x) return false;
    }
    // 检查列
    for (int i = 0; i < 9; i++) {
        if (board[i][row] == x) return false;
    }
    // 检查3x3子网格
    int startCol = (col / 3) * 3;
    int startRow = (row / 3) * 3;
    for (int i = startCol; i < startCol + 3; i++) {
        for (int j = startRow; j < startRow + 3; j++) {
            if (board[i][j] == x) return false;
        }
    }
    return true;
}

// 回溯函数：递归填充数独板
bool dfs(char **board, int boardSize, int col, int row) {
    // 遍历数独板的每个格子
    for (int i = col; i < boardSize; i++) {
        for (int j = row; j < boardSize; j++) {
            // 如果当前格子为空
            if (board[i][j] == '.') {
                // 尝试填入1到9的数字
                for (char k = '1'; k <= '9'; k++) {
                    // 检查当前数字是否合法
                    if (isvaild(board, i, j, k)) {
                        // 填入数字
                        board[i][j] = k;
                        // 递归填充下一个格子
                        if (dfs(board, boardSize, i, j)) {
                            return true; // 找到解，提前返回
                        }
                        // 回溯：撤销当前选择
                        board[i][j] = '.';
                    }
                }
                return false; // 当前格子无解，触发回溯
            }
        }
        row = 0; // 重置列索引，确保从下一行的开头开始
    }
    return true; // 所有格子填充完毕，找到解
}

// 主函数：解决数独问题
void solveSudoku(char **board, int boardSize, int *boardColSize) {
    for(int i=0;i<9;i++)boardColSize[i]=9;
    dfs(board, boardSize, 0, 0);
    return;
}

startCol = (col / 3) * 3;
int startRow = (row / 3) * 3;
for (int i = startCol; i < startCol + 3; i++) {
for (int j = startRow; j < startRow + 3; j++) {
if (board[i][j] == x) return false;
}
}
return true;
}

// 回溯函数：递归填充数独板
bool dfs(char **board, int boardSize, int col, int row) {
// 遍历数独板的每个格子
for (int i = col; i < boardSize; i++) {
for (int j = row; j < boardSize; j++) {
// 如果当前格子为空
if (board[i][j] == ‘.’) {
// 尝试填入1到9的数字
for (char k = ‘1’; k <= ‘9’; k++) {
// 检查当前数字是否合法
if (isvaild(board, i, j, k)) {
// 填入数字
board[i][j] = k;
// 递归填充下一个格子
if (dfs(board, boardSize, i, j)) {
return true; // 找到解，提前返回
}
// 回溯：撤销当前选择
board[i][j] = ‘.’;
}
}
return false; // 当前格子无解，触发回溯
}
}
row = 0; // 重置列索引，确保从下一行的开头开始
}
return true; // 所有格子填充完毕，找到解
}

// 主函数：解决数独问题
void solveSudoku(char **board, int boardSize, int *boardColSize) {
for(int i=0;i<9;i++)boardColSize[i]=9;
dfs(board, boardSize, 0, 0);
return;
}