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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */

void swap(int* a,int* b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}

bool shouldskip(int* num,int start,int i){
    for(int j=start;j<i;j++){
        if(num[j]==num[i])return true;
    }
    return false;
}

void backtrack(int* num,int numLen,int n,int* returnsize,int* returnColumnSizes,int** result){
    if(n==numLen){
        result[*returnsize]=malloc(sizeof(int)*numLen);
        returnColumnSizes[*returnsize]=numLen;
        for(int i=0;i<numLen;i++){
            result[*returnsize][i]=num[i];
        }
        (*returnsize)++;
        return;
    }
    for(int i=n;i<numLen;i++){
        if(shouldskip(num,n,i))continue;//检查是否有重复数字比如1.1.2这种
        swap(num+i,num+n);
        backtrack(num,numLen,n+1,returnsize,returnColumnSizes,result);
        swap(num+i,num+n);
    }
}

int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int n=1;
    //阶乘算出总共有多少种排列组合
    for(int i=1;i<=numLen;i++){
        n=n*i;
    }
    int** result=(int**)malloc(sizeof(int*)*n);
    *returnColumnSizes=malloc(sizeof(int)*n);
    *returnSize=0;
    backtrack(num,numLen,0,returnSize,*returnColumnSizes,result);
    return result;
}