Leecode刷题C语言之全排列②

执行结果:通过

执行用时和内存消耗如下：

int* path;
int pathTop;
int** ans;
int ansTop;
int cnt[8];//标记path中是否已有此索引值，这也是同46题不同点
void backTracking(int* nums,int numsSize,int startIndex,int** returnColumnSizes){
    if(pathTop==numsSize){
        (*returnColumnSizes)[ansTop] = pathTop;
        ans[ansTop] = (int*)malloc(sizeof(int)*pathTop);
        for(int i = 0;i<pathTop;i++){//装入子集
            ans[ansTop][i] = path[i];
        }
        ansTop++;
        return;
    }
    int cnt_1[21];//同一层相同元素只能读一次
    memset(cnt_1,0,sizeof(cnt_1));
    //递归组合
    for(int i = startIndex;i<numsSize;i++){
        if(cnt[i]||cnt_1[nums[i]+10]) continue;//此索引本轮已访问过或此值在此层已访问过
        path[pathTop++] = nums[i];
        cnt[i] = 1;//本组合相应索引位置已访问
        cnt_1[nums[i]+10] = 1;//本层相同元素已访问
        backTracking(nums,numsSize,0,returnColumnSizes);
        cnt[i] = 0;//退出路径则解除标记
        pathTop--;
    }
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    memset(cnt,0,sizeof(cnt));
    path = (int*)malloc(sizeof(int)*8);//开到最大
    ans = (int**)malloc(sizeof(int*)*10000);
    *returnColumnSizes = (int*)malloc(sizeof(int)*10000);
    pathTop = 0;
    ansTop = 0;
    //从0开始递归
    backTracking(nums,numsSize,0,returnColumnSizes);
    *returnSize = ansTop;
    free(path);
    return ans;
}

解题思路：

这段代码实现的是求解给定整数数组 nums 的所有不重复排列的算法。它使用了回溯算法（Backtracking）来解决这个问题。以下是解题思路的详细步骤：

1. 初始化变量:
   • int* path;：用于存储当前排列路径。
   • int pathTop;：表示当前路径中的元素数量。
   • int** ans;：用于存储所有排列的结果。
   • int ansTop;：表示结果中排列的数量。
   • int cnt[8];：用于标记在 path 中是否已有某个索引值，防止在同一排列中重复使用同一元素（由于题目可能未明确数组大小，这里假设最大为8，实际应用中应根据具体情况调整）。
2. 辅助函数 backTracking:
   • 参数：int* nums（输入数组），int numsSize（数组大小），int startIndex（当前递归的起始索引），int** returnColumnSizes（用于存储每个排列的长度）。
   • 终止条件：当 pathTop == numsSize 时，表示找到一个完整排列，将其存储到 ans 中，并更新 ansTop 和 *returnColumnSizes。
3. 去重机制:
   • 在每一层递归中，使用一个临时数组 cnt_1[21]（考虑到 nums[i] 可能为负数，所以偏移10以避免数组越界）来记录当前层已经访问过的元素值，防止在同一层中重复使用相同的元素值。
   • cnt 数组用于记录在整个排列过程中，某个索引是否已经访问过，防止在排列中重复使用同一元素。
4. 递归过程:
   • 从 startIndex 开始遍历数组 nums。
   • 如果当前元素索引已被访问过（cnt[i]）或当前元素值在同一层已被访问过（cnt_1[nums[i]+10]），则跳过该元素。
   • 将当前元素加入 path，标记该索引和该元素值已被访问。
   • 递归调用 backTracking，注意下一层递归的 startIndex 应为0，因为我们需要考虑所有元素的所有可能位置，而不是仅考虑剩余元素。
   • 回溯：撤销选择，即将当前元素从 path 中移除，并取消对该索引和元素值的标记。
5. 主函数 permuteUnique:
   • 初始化 cnt 数组、path 数组、ans 数组和 *returnColumnSizes。
   • 调用 backTracking 函数开始递归。
   • 设置 *returnSize 为 ansTop，即排列的总数。
   • 释放 path 数组的内存，返回 ans 数组。
6. 内存管理:
   • 注意在返回结果之前，所有动态分配的内存（如 path 和 ans 中的每个排列）都应当被正确管理。在这个实现中，path 在返回结果前被释放，但返回的 ans 数组及其内容需要由调用者负责释放，以避免内存泄漏。

这个算法的关键在于通过 cnt 和 cnt_1 两个数组来有效地避免生成重复的排列，同时通过回溯算法确保能够遍历所有可能的排列。