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

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

#include <stdio.h>
#include <malloc.h>

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

void re_permute(int* num, int index, int numLen, int* returnSize, int** returnColumnSizes, int** res) {
    int i = 0;
    // 索引到最后一位的时候，将num数组赋值给当前行数组
    if(index == numLen) {
        res[*returnSize] = (int*)malloc(numLen * sizeof(int));
        for(int i = 0; i < numLen; i++) {
            res[*returnSize][i] = num[i];
        }
        (*returnColumnSizes)[*returnSize] = numLen;
        (*returnSize)++;
    }

    for(i = index; i < numLen; i++) {
        swap(&num[i], &num[index]);
        if((numLen - index) > 2 && index != i) {
            swap(&num[i], &num[index + 1]);
            re_permute(num, index + 1, numLen, returnSize, returnColumnSizes, res);
            swap(&num[i], &num[index + 1]);
        } else {
            re_permute(num, index + 1, numLen, returnSize, returnColumnSizes, res);
        }
        swap(&num[i], &num[index]);
    }
}


int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    if(numLen == 0) {return NULL;}
    int i = 1;
    int count = 1;
    for(; i <= numLen; i++) {
        count *= i;
    }
    *returnColumnSizes = (int*)malloc(count * sizeof(int));
    int** res = (int**)malloc(count * sizeof(int*));
    *returnSize = 0;
    re_permute(num, 0, numLen, returnSize, returnColumnSizes, res);
    return res;
}