TOP101题解 | BM56#有重复项数字的全排列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.26
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
#include <stdlib.h>
int compar(const void* p1, const void* p2)
{
    return (*(int*)p1 - *(int*)p2);
}

void backtrack(int* nums, int numsLen, int* visited, int* path, int depth, int** result, int* returnSize) 
{
    if (depth == numsLen) 
    {
        result[*returnSize] = (int*)malloc(sizeof(int) * numsLen);
        memcpy(result[*returnSize], path, sizeof(int) * numsLen);
        (*returnSize)++;
        return;
    }
    
    for (int i = 0; i < numsLen; i++) 
    {
        if (!visited[i]) 
        {
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) 
            {
                continue; // 剪枝，避免生成重复排列
            }
            path[depth] = nums[i];
            visited[i] = 1;
            backtrack(nums, numsLen, visited, path, depth + 1, result, returnSize);
            visited[i] = 0;
        }
    }
}

int** permuteUnique(int* num, int numLen, int* returnSize, int** returnColumnSizes) 
{   //write code here
    int totalPermutations = 1;
    for (int i = 1; i <= numLen; i++) 
    {
        totalPermutations *= i;
    }
    
    int** result = (int**)malloc(sizeof(int*) * totalPermutations);
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(sizeof(int) * totalPermutations);
    
    int* visited = (int*)calloc(numLen, sizeof(int));
    int* path = (int*)malloc(sizeof(int) * numLen);
    
    // 首先对数组进行排序，以确保重复的数字相邻
    qsort(num, numLen, sizeof(int), compar);
    
    backtrack(num, numLen, visited, path, 0, result, returnSize);
    
    free(visited);
    free(path);
    
    for (int i = 0; i < *returnSize; i++) 
    {
        (*returnColumnSizes)[i] = numLen;
    }
    
    return result;
}

Tips:

在前一题的基础上剪枝就可以了