递归实现LeetCode22括号生成时的堆缓冲区溢出问题求助

一、核心问题定位方向 #

• 字符串内存分配未预留终止符空间：括号生成的字符串长度固定为2*n，若仅分配2*n字节而非2*n+1（未给\0留位置），后续字符串操作必然越界
• 递归回溯时的内存操作错误：递归分支中重复释放同一块内存、或部分分支未释放临时内存，会破坏堆结构引发溢出
• 字符串操作边界失控：即便用calloc初始化，若strcpy/strcat的目标缓冲区剩余空间不足，依然会触发溢出

二、借助工具精准定位的步骤 #

1. 用AddressSanitizer快速定位：编译时添加调试符号与地址 sanitizer：gcc -g -fsanitize=address your_code.c -o your_program，运行程序会直接输出精确的越界代码行与堆栈跟踪，效率远高于Valgrind
2. Valgrind详细日志分析：执行valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes ./your_program，重点关注Invalid write of size X条目，其后续的堆栈跟踪会直接指向越界写入的代码位置
3. 递归层日志排查：在递归函数中添加日志，打印当前字符串长度、缓冲区已分配大小，观察是否出现长度超过缓冲区的情况

三、代码修复示例（针对内存问题） #

以下是修复后的递归实现，解决了堆溢出核心问题：

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

void generate(char **result, int *count, char *current, int open, int close, int n) {
    // 字符串长度达标时存入结果
    if (strlen(current) == 2 * n) {
        // 分配内存必须包含终止符位置：2n+1字节
        result[*count] = malloc((2 * n + 1) * sizeof(char));
        strcpy(result[*count], current);
        (*count)++;
        return;
    }

    if (open < n) {
        int len = strlen(current);
        current[len] = '(';
        current[len + 1] = '\0'; // 手动添加终止符，避免未定义行为
        generate(result, count, current, open + 1, close, n);
        current[len] = '\0'; // 回溯恢复原字符串
    }

    if (close < open) {
        int len = strlen(current);
        current[len] = ')';
        current[len + 1] = '\0';
        generate(result, count, current, open, close + 1, n);
        current[len] = '\0'; // 回溯恢复
    }
}

char** generateParenthesis(int n, int* returnSize) {
    // 预计算结果数组最大容量（卡特兰数：C(2n,n)/(n+1)）
    int max_count = 1;
    for (int i = 2; i <= 2*n; i++) 
        max_count = max_count * i / ((i <= n) ? i : i - n);
    
    char **result = malloc(max_count * sizeof(char*));
    *returnSize = 0;

    // 初始化当前字符串缓冲区：预留2n+1字节空间
    char *current = calloc(2 * n + 1, sizeof(char));
    generate(result, returnSize, current, 0, 0, n);
    free(current); // 释放临时缓冲区

    return result;
}

// 测试用例
int main() {
    int returnSize;
    char **res = generateParenthesis(3, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", res[i]);
        free(res[i]);
    }
    free(res);
    return 0;
}

修复关键点：

• 所有字符串分配时预留2*n+1字节，确保容纳终止符
• 递归回溯时手动恢复字符串终止符，避免后续操作越界
• 预计算结果数组的最大容量，防止结果数组溢出
• 调试编译启用AddressSanitizer，快速定位潜在问题

四、高效排查heap-buffer-overflow的通用方法 #

• 优先用AddressSanitizer：编译加-fsanitize=address，运行时直接抛出越界的代码行与堆栈，定位效率远高于Valgrind
• 手动校验内存分配大小：字符串操作前，确认目标缓冲区剩余空间足够容纳写入内容（含终止符）
• GDB调试崩溃现场：程序崩溃时，用gdb ./your_program加载二进制，执行run触发崩溃后，用bt查看堆栈跟踪，定位出错的递归调用层
• 边界条件测试：用最小测试用例（如n=1、n=2）运行，观察是否触发溢出，缩小问题范围

内容的提问来源于stack exchange，提问作者khamun7