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

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

/*复刻了b站一位大佬的递归回溯，但是这里要返回值，他是直接打印，不会语法申请空间和传参疯狂报错人麻了
外层交换 |字典序内层交换-回溯（横向为递归层次，纵向为同一层内的循环）
1 2 3 4 |1 2 3 4 |1 2 3 4 |1 2 3 4
-      ->  -    ->    -  ->      -
2 1 3 4 |1 3 2 4 |1 2 4 3 |return ;
- -        - -        - -
3 2 1 4 |1 4 3 2 |
-   -      -   - 
4 2 3 1 |
-     -
*/
// void swap(int num[],int i,int j){//全排序只需要依次交换、回溯
//     int temp=num[i];
//     num[i]=num[j];
//     num[j]=temp;
// }
void swap(int num[],int begin,int end){
    int temp=num[end];//存储最后一个元素，整体右移，然后放到begin
    for(int k=end;k>begin;k--){//1 2 3 4->3 1 2 4|1 2 3 4->4 1 2 3保证子序列升序
        num[k]=num[k-1];//[begin,end]begin k->end begin
    }
    num[begin]=temp;
}


void swapback(int num[],int begin,int end){//字典序排列-回溯到层次内元素有序
    int temp=num[begin];//第一个元素是被交换过的，重新存储，整体左移，放回最后
    for(int k=begin;k<end;k++){//[begin,end](end传参传的是本次被交换的末尾结点下标i，而不是长度)
        num[k]=num[k+1];//k end->end begin
    }
    num[end]=temp;//回溯到本轮初始状态
}

void perm(int num[],int begin,int end,int **Res,int* row){
    if(begin==end){
        //得到序列，存入
        memcpy(Res[*row],num,end*sizeof(int));//复制内存(目标地址，源地址，空间大小)
        (*row)++;
    }
    else{
        for(int i=begin;i<end;i++){//[begin,end-1]
            swap(num,begin,i);//遍历本层次每个元素作为第一位的情况
            perm(num,begin+1,end,Res,row);//去除当前位，对剩余位全排列
            swapback(num,begin,i);//回溯到本轮元素有序
//            swap(num,begin,i);
        }
    }

}

int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int sum=1;
    int j=1;
    while(j<=numLen){//求阶乘 排序种类
        sum*=j++;
    }
    *returnSize=sum;
    *returnColumnSizes=(int*)malloc(sizeof(int)*sum);//必须分配列空间！！！
    for(int i=0;i<sum;i++){
        (*returnColumnSizes)[i]=numLen;//(*a)[]表示a的行中的元素，*a[]表示访问a的元素指向的地址，但元素又没有存地址
    }
    int **Res=(int**)malloc(sizeof(int*)*sum);//二维数组空间(**指针的指针/二维)malloc(sizeof(*行指针？)*长度)
    for(int j=0;j<sum;j++){
        Res[j]=(int*)malloc(sizeof(int)*numLen);//为每行申请空间
    }
    int row=0;//传参的时候用引用可以取变量地址
    //求全排序->字典序排列
    perm(num,0,numLen,Res,&row);
    return Res;
}