LeetCode 46题中int** returnColumnSizes含义与代码修复咨询

问题背景 #

我是C语言初学者，正在练习指针与malloc相关技能，当前在解决LeetCode 46题（全排列）时遇到问题：给定由不同整数组成的数组nums，返回所有可能的排列，返回顺序不限。

我的代码在VS Code的示例测试中能正常运行，但提交至LeetCode时出现错误：

Line 241: Char 15: runtime error: load of null pointer of type 'int' [Serializer.c]

我推测问题出在未正确处理函数签名中的最后一个参数int** returnColumnSizes，但不清楚这个二级指针的具体含义，希望得到代码改进建议和正确解题思路。

函数签名困惑点 #

LeetCode提供的固定函数签名为：

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)

其中returnColumnSizes是二级指针，作用是返回每个子排列数组的长度：

• 你需要malloc一个int数组，数组长度等于*returnSize（即排列的总数）
• 数组中的每个元素对应返回结果数组中对应子数组的列数（这里每个排列的长度都是numsSize，所以所有元素都赋值为numsSize）
• 最后把这个数组的地址赋值给*returnColumnSizes，让调用者能获取每个子数组的长度信息

现有代码 #

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

/**
 * 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().
 */

/*
numsSize is max 6.
*/
void backTrack(int** res, int* nums, int numsSize, int* permutation, int permutationSize, bool* used, int* numberadded);

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {

    // Determine returnSize
    int factorialLookUpTable[6] = {1,2,6,24,120,720};
    *returnSize = factorialLookUpTable[numsSize-1];

    // Malloc
    int **returnedArray = malloc(sizeof(int*)* (*returnSize)); // An array that hold 'returnSize' pointers.

    // Inititalizing the arrays inside returnedArray
    for(int i = 0; i< *returnSize; i++){
        returnedArray[i] = malloc(sizeof(int)* numsSize);
    }

    int* permutation = malloc(numsSize*sizeof(int));
    bool* used = calloc(numsSize, sizeof(bool));
    int numberAdded = 0;

    backTrack(returnedArray, nums, numsSize, permutation, 0, used, &numberAdded);

    return returnedArray;
    
}

void backTrack(int** res, int* nums, int numsSize, int* permutation, int permutationSize, bool* used, int* numberadded){


    if (permutationSize == numsSize){
        // Add the permutation to the result.
        memcpy(res[*numberadded],permutation,numsSize*sizeof(int));
        *numberadded += 1;
        return;

    }

    // Go through all digits and combinations.
    for (int i = 0; i < numsSize; i++){
        if (! used[i]){

            used[i] = true;
            permutation[permutationSize] = nums[i];
            permutationSize++;

            backTrack(res, nums, numsSize, permutation, permutationSize, used, numberadded); // recursion

            used[i] = false;
            permutation[permutationSize-1] = 0;
            permutationSize--;

        }
        
    }

}

错误原因与代码改进 #

错误核心 #

未对returnColumnSizes进行内存分配和赋值，导致LeetCode的序列化代码尝试访问空指针，触发运行时错误。

改进后的代码 #

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

void backTrack(int** res, int* nums, int numsSize, int* permutation, int permutationSize, bool* used, int* numberadded);

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 计算排列总数
    int factorialLookUpTable[6] = {1,2,6,24,120,720};
    *returnSize = factorialLookUpTable[numsSize-1];

    // 分配结果数组内存
    int **returnedArray = malloc(sizeof(int*)* (*returnSize));
    for(int i = 0; i< *returnSize; i++){
        returnedArray[i] = malloc(sizeof(int)* numsSize);
    }

    // 处理returnColumnSizes：分配内存并赋值每个子数组长度
    *returnColumnSizes = malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i < *returnSize; i++){
        (*returnColumnSizes)[i] = numsSize;
    }

    int* permutation = malloc(numsSize*sizeof(int));
    bool* used = calloc(numsSize, sizeof(bool));
    int numberAdded = 0;

    backTrack(returnedArray, nums, numsSize, permutation, 0, used, &numberAdded);

    // 释放临时内存，避免泄漏
    free(permutation);
    free(used);

    return returnedArray;
}

void backTrack(int** res, int* nums, int numsSize, int* permutation, int permutationSize, bool* used, int* numberadded){
    if (permutationSize == numsSize){
        memcpy(res[*numberadded], permutation, numsSize*sizeof(int));
        *numberadded += 1;
        return;
    }

    for (int i = 0; i < numsSize; i++){
        if (!used[i]){
            used[i] = true;
            permutation[permutationSize] = nums[i];
            backTrack(res, nums, numsSize, permutation, permutationSize+1, used, numberadded);
            // 回溯：撤销选择
            used[i] = false;
            // 这里不需要把permutation设为0，后续会被覆盖，可省略
            // permutation[permutationSize] = 0;
        }
    }
}

关键改进点 #

1. 处理returnColumnSizes：分配对应长度的int数组，每个元素赋值为numsSize，然后将数组地址赋值给*returnColumnSizes
2. 释放临时内存：回溯完成后，释放permutation和used的内存，避免内存泄漏
3. 简化回溯代码：去掉了多余的permutationSize++和--，直接在递归调用时传递permutationSize+1，逻辑更简洁

解题思路梳理 #

采用回溯法生成全排列，核心逻辑：

• 用used数组标记当前已选择的元素，避免重复使用
• 用permutation数组临时存储当前正在构建的排列
• 当permutation的长度等于numsSize时，说明生成了一个完整排列，将其复制到结果数组中
• 递归回溯：每次选择一个未使用的元素，标记为已使用，递归进入下一层；递归返回后，撤销标记，尝试下一个元素

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