力扣hot100——回溯

文章目录 前言55.全排列题目描述思路：DFS+回溯code 56.子集题目描述思路：dfs+回溯code 57.电话号码的字母组合题目描述思路：DFS+回溯code 58.数组总和题目描述题目描述code 59.括号生成题目描述思路：DFS+回溯code 60.单词搜索题目描述思路：DFS+回溯code 61.分割回文串题目描述思路：DFS+回溯code 62.N皇后题目描述思路code

前言

大部分题目是代码随想录已经刷过的题，更多的回溯题可以看之前的博客。

55.全排列 题目描述

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1] 输出：[[1]]

提示：

1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不相同 思路：DFS+回溯 使用 回溯算法 来生成所有可能的排列。通过递归遍历数组中的每个元素，尝试将其加入当前路径中，直到路径长度等于数组长度。使用一个 used 数组来记录哪些元素已经被使用过，避免重复选择。 code #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> /** * 回溯递归函数 * @param nums: 输入数组 * @param numsSize: 数组长度 * @param path: 当前路径 * @param pathSize: 当前路径长度 * @param ans: 结果数组 * @param returnSize: 结果数组的长度 * @param returnColumnSizes: 结果数组中每个排列的长度 * @param used: 记录元素是否被使用过 */ void dfs(int* nums, int numsSize, int* path, int pathSize, int** ans, int* returnSize, int** returnColumnSizes, bool* used) { // 如果当前路径长度等于数组长度，说明找到一个排列 if (pathSize == numsSize) { // 分配内存存储当前排列 ans[(*returnSize)] = malloc(sizeof(int) * numsSize); // 记录当前排列的长度 (*returnColumnSizes)[(*returnSize)] = numsSize; // 将路径复制到结果中 for (int i = 0; i < numsSize; i++) { ans[(*returnSize)][i] = path[i]; } // 结果数组长度加 1 (*returnSize)++; return; } // 遍历数组中的每个元素 for (int i = 0; i < numsSize; i++) { // 如果当前元素未被使用 if (!used[i]) { used[i] = true; // 标记为已使用 path[pathSize] = nums[i]; // 将当前元素加入路径 // 递归处理下一个位置 dfs(nums, numsSize, path, pathSize + 1, ans, returnSize, returnColumnSizes, used); used[i] = false; // 回溯，撤销选择 } } } /** * 全排列函数 * @param nums: 输入数组 * @param numsSize: 数组长度 * @param returnSize: 返回结果数组的长度 * @param returnColumnSizes: 返回结果数组中每个排列的长度 * @return: 返回所有排列的结果 */ int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { // 计算所有可能的排列总数（numsSize 的阶乘） int total = 1; for (int i = 2; i <= numsSize; i++) total *= i; // 分配内存存储结果 int** ans = malloc(sizeof(int*) * total); // 分配内存存储路径 int* path = malloc(sizeof(int) * numsSize); // 初始化结果数组长度 *returnSize = 0; // 分配内存存储每个排列的长度 *returnColumnSizes = malloc(sizeof(int) * total); // 初始化 used 数组，记录元素是否被使用过 bool used[numsSize]; memset(used, false, sizeof(used)); // 调用回溯函数生成所有排列 dfs(nums, numsSize, path, 0, ans, returnSize, returnColumnSizes, used); // 返回结果 return ans; } 56.子集 题目描述

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0] 输出：[[],[0]]

提示：

1 <= nums.length <= 10-10 <= nums[i] <= 10nums 中的所有元素 互不相同 思路：dfs+回溯

使用 回溯算法 来生成所有可能的子集。

对于数组中的每个元素，有两种选择：

将其加入当前子集。

不将其加入当前子集。

通过递归遍历所有可能的选择，直到处理完所有元素。

code /** * 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(). */ #include <stdio.h> #include <stdlib.h> /** * 回溯递归函数 * @param nums: 输入数组 * @param numsSize: 数组长度 * @param path: 当前路径 * @param pathSize: 当前路径长度 * @param index: 当前处理的元素索引 * @param ans: 结果数组 * @param returnSize: 结果数组的长度 * @param returnColumnSizes: 结果数组中每个子集的长度 */ void dfs(int* nums, int numsSize, int* path, int pathSize, int index, int** ans, int* returnSize, int** returnColumnSizes) { // 如果当前索引等于数组长度，说明找到一个子集 if (index == numsSize) { // 分配内存存储当前子集 ans[(*returnSize)] = malloc(sizeof(int) * pathSize); // 将路径复制到结果中 for (int i = 0; i < pathSize; i++) { ans[(*returnSize)][i] = path[i]; } // 记录当前子集的长度 (*returnColumnSizes)[(*returnSize)] = pathSize; // 结果数组长度加 1 (*returnSize)++; return; } // 选择将当前元素加入路径 path[pathSize] = nums[index]; dfs(nums, numsSize, path, pathSize + 1, index + 1, ans, returnSize, returnColumnSizes); // 选择不将当前元素加入路径 dfs(nums, numsSize, path, pathSize, index + 1, ans, returnSize, returnColumnSizes); } /** * 子集函数 * @param nums: 输入数组 * @param numsSize: 数组长度 * @param returnSize: 返回结果数组的长度 * @param returnColumnSizes: 返回结果数组中每个子集的长度 * @return: 返回所有子集的结果 */ int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { // 初始化结果数组长度 *returnSize = 0; // 计算所有可能的子集总数（2^n） int total = 1; for (int i = 0; i < numsSize; i++) total *= 2; // 分配内存存储结果 *returnColumnSizes = malloc(sizeof(int) * total); int** ans = malloc(sizeof(int*) * total); // 分配内存存储路径 int* path = malloc(sizeof(int) * numsSize); // 调用回溯函数生成所有子集 dfs(nums, numsSize, path, 0, 0, ans, returnSize, returnColumnSizes); // 返回结果 return ans; } 57.电话号码的字母组合 题目描述

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = "" 输出：[]

示例 3：

输入：digits = "2" 输出：["a","b","c"]

提示：

0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。 思路：DFS+回溯

对于每个数字，先找到其可以替换的字母，再用DFS遍历所有可能，知道最后一个数字被替换，添加到答案中。我认为本题实现有些难度。

code // 数字到字母的映射 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; // 返回结果数组 } 58.数组总和 题目描述

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1 输出: []

提示：

1 <= candidates.length <= 302 <= candidates[i] <= 40candidates 的所有元素 互不相同1 <= target <= 40 题目描述 使用 回溯算法 来生成所有可能的组合。通过递归遍历数组中的每个元素，尝试将其加入当前路径中，直到路径和等于目标数。使用 start 参数避免重复组合。 code /** * 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; } 59.括号生成 题目描述

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1 输出：["()"]

提示：

1 <= n <= 8 思路：DFS+回溯

回溯：

使用 回溯算法 来生成所有可能的括号组合。通过递归遍历所有可能的选择，确保生成的括号组合是有效的。使用两个变量 leftnum 和 rightnum 分别记录当前路径中左括号和右括号的数量。在递归过程中，确保以下条件： 左括号的数量不超过 n。右括号的数量不超过左括号的数量。 code #include <stdio.h> #include <stdlib.h> /** * 回溯递归函数 * @param n: 括号对数 * @param leftnum: 当前路径中左括号的数量 * @param rightnum: 当前路径中右括号的数量 * @param path: 当前路径 * @param pathSize: 当前路径长度 * @param ans: 结果数组 * @param returnSize: 结果数组的长度 */ void dfs(int n, int leftnum, int rightnum, char* path, int pathSize, char** ans, int* returnSize) { // 如果当前路径长度等于 2 * n，说明找到一个有效组合 if (pathSize == 2 * n) { // 分配内存存储当前组合 ans[(*returnSize)] = malloc(sizeof(char) * (2 * n + 1)); // 将路径复制到结果中 for (int i = 0; i < 2 * n; i++) { ans[(*returnSize)][i] = path[i]; } // 添加字符串结束符 ans[*returnSize][2 * n] = '\0'; // 结果数组长度加 1 (*returnSize)++; return; } // 如果左括号数量小于右括号数量，直接返回（无效组合） if (leftnum < rightnum) return; // 如果左括号数量等于右括号数量，只能添加左括号 if (leftnum == rightnum) { path[pathSize] = '('; dfs(n, leftnum + 1, rightnum, path, pathSize + 1, ans, returnSize); } // 如果左括号数量大于右括号数量 else { // 添加右括号 path[pathSize] = ')'; dfs(n, leftnum, rightnum + 1, path, pathSize + 1, ans, returnSize); // 如果左括号数量小于 n，可以添加左括号 if (leftnum < n) { path[pathSize] = '('; dfs(n, leftnum + 1, rightnum, path, pathSize + 1, ans, returnSize); } } } /** * 生成有效括号组合函数 * @param n: 括号对数 * @param returnSize: 返回结果数组的长度 * @return: 返回所有有效的括号组合 */ char** generateParenthesis(int n, int* returnSize) { // 分配内存存储结果 char** ans = malloc(sizeof(char*) * 2000); // 分配内存存储路径 char* path = malloc(sizeof(char) * (2 * n + 1)); // 初始化结果数组长度 *returnSize = 0; // 调用回溯函数生成所有有效组合 dfs(n, 0, 0, path, 0, ans, returnSize); // 返回结果 return ans; } 60.单词搜索 题目描述

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false

提示：

m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board 和 word 仅由大小写英文字母组成

**进阶：**你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

思路：DFS+回溯

回溯：

如果所有字符都匹配，返回 true。遍历四个方向，检查新位置是否在网格范围内、未被访问过且字符匹配。如果匹配，则递归查找下一个字符。如果递归返回 true，则返回 true。否则，回溯并撤销标记 code #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> // 方向数组：上下左右 int direction[4][2] = { {-1, 0}, // 上 {1, 0}, // 下 {0, -1}, // 左 {0, 1} // 右 }; /** * 深度优先搜索（DFS）函数 * @param board: 二维字符网格 * @param m: 网格的行数 * @param n: 网格的列数 * @param vis: 访问标记数组 * @param x: 当前单元格的行索引 * @param y: 当前单元格的列索引 * @param word: 目标单词 * @param wordIndex: 当前匹配的字符索引 * @return: 是否找到单词 */ bool dfs(char** board, int m, int n, bool** vis, int x, int y, char* word, int wordIndex) { // 如果所有字符都匹配，返回 true if (word[wordIndex] == '\0') return true; // 遍历四个方向 for (int i = 0; i < 4; i++) { int nx = x + direction[i][0]; int ny = y + direction[i][1]; // 检查新位置是否在网格范围内，且未被访问过，且字符匹配 if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && board[nx][ny] == word[wordIndex]) { vis[nx][ny] = true; // 标记为已访问 if (dfs(board, m, n, vis, nx, ny, word, wordIndex + 1)) return true; vis[nx][ny] = false; // 回溯，撤销标记 } } return false; } /** * 单词搜索函数 * @param board: 二维字符网格 * @param boardSize: 网格的行数 * @param boardColSize: 网格的列数数组 * @param word: 目标单词 * @return: 是否找到单词 */ bool exist(char** board, int boardSize, int* boardColSize, char* word) { int m = boardSize; // 网格的行数 int n = boardColSize[0]; // 网格的列数 // 分配并初始化访问标记数组 bool** vis = malloc(sizeof(bool*) * m); for (int i = 0; i < m; i++) { vis[i] = malloc(sizeof(bool) * n); memset(vis[i], false, sizeof(bool) * n); } // 遍历网格中的每个单元格 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 如果当前单元格的字符与单词的第一个字符匹配 if (board[i][j] == word[0]) { vis[i][j] = true; // 标记为已访问 if (dfs(board, m, n, vis, i, j, word, 1)) { // 释放内存 for (int k = 0; k < m; k++) free(vis[k]); free(vis); return true; } vis[i][j] = false; // 回溯，撤销标记 } } } // 释放内存 for (int i = 0; i < m; i++) free(vis[i]); free(vis); return false; } 61.分割回文串 题目描述

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a" 输出：[["a"]]

提示：

1 <= s.length <= 16s 仅由小写英文字母组成 思路：DFS+回溯

使用回溯算法遍历所有可能的分割方式。

在每一层递归中，尝试从当前位置开始分割出一个回文子串。

如果当前子串是回文，则将其加入路径，并递归处理剩余部分。

如果当前分割位置到达字符串末尾，说明找到一种有效的分割方案，将其保存到结果中。

code // 判断子串 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; // 返回所有有效的分割方案 } 62.N皇后 题目描述

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1 输出：[["Q"]]

提示：

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

个人感觉难度和之前的回溯题差不多，但力扣给的是难度等级是困难。。。

code #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); // 释放路径数组的内存 free(path); return res; }