代码随想录——回溯

组合

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)++;  // 结果数组的索引加 1return;}//剪枝，也可以不加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)++;  // 结果数组的索引加 1return;}// 如果当前和已经小于 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)++;  // 结果数组的索引加 1return;}// 获取当前数字对应的字母集合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)++; // 有效分割方案数量加 1return;}// 尝试从当前位置开始分割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 地址数量为 0char **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);// 为路径数组分配内存，假设最大路径长度为6int *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]); // 起点IDtickets_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 开始执行 DFSdfs("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)++; // 解的数量加1return;}// 尝试在当前行的每一列放置皇后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;
}