文章目录
- 前言
- 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;
}
![【PyTorch][chapter-33][transformer-5] MHA MQA GQA, KV-Cache](https://i-blog.csdnimg.cn/direct/34e9af41b1bb41fb94b2e235bc87ed38.png)
