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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @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 <string.h>
void backtrack(int* num, int numLen,int* flag, int* path, int depth, int** result ,int* returnSize)
{
    /*层数为长度时,即结束*/
    if(depth == numLen)
    {
        // result[*returnSize] = (int*)malloc(sizeof(int) * numsLen);
        // memcpy(result[*returnSize], path, sizeof(int) * numsLen);
        // (*returnSize)++;
        result[(*returnSize)++] = path;
        return ;
    }
    else 
    {
        for(int i = 0; i < numLen; i++)
        {
            if(!flag[i])/*未标记*/
            {
                path[depth] = num[i];/*记录元素*/
                flag[i] = 1;/*该元素打上标记*/
                backtrack(num, numLen, flag, path, depth + 1, result, returnSize);/*递归*/
                flag[i] = 0;/*该depth位使用元素num[i],使用完后清除标记*/
            }
        }
    }
}

int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) 
{
    // write code here
    /*算出n!即排列组合的个数*/
    int total = 1;
    for(int i = 1; i <= numLen; i++)
    {
        total *= i;
    }
    
    *returnSize = 0;/*初始为0*/
    *returnColumnSizes = (int*)malloc(total * sizeof(int));
    
    int* flag = (int*)calloc(numLen,sizeof(int));/*标记数组,初始默认为0*/

    int** result = (int**)malloc(total * sizeof(int*));/*结果数组*/
    int* path = (int*)malloc(numLen * sizeof(int));/*结果路径,每条路径都会保存在结果数组中*/

    backtrack(num, numLen, flag, path, 0, result, returnSize);

    for (int i = 0; i < *returnSize; i++) 
    {
        (*returnColumnSizes)[i] = numLen;
    }

    return result;
}