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

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


#include <stdio.h>
#include <stdlib.h>

void backsearch(int *num, int numLen, int *count, int **totalSeq, int* state, _Bool* visited, int stateLen) {
    if(stateLen == numLen) {
        totalSeq[*count] = (int*)malloc(numLen * sizeof(int));
        for(int i = 0; i < numLen; i++) {
            totalSeq[*count][i] = state[i];
            printf("%d ", state[i]);
        }
        printf("\n");
        *count += 1;
        return;
    }

    _Bool duplicated[7] = {0};
    for(int i = 0; i < numLen; i++) {
        if(!visited[i] && !duplicated[num[i] + 1]) {
            state[stateLen] = num[i];
            visited[i] = 1;
            duplicated[num[i] + 1] = 1;
            backsearch(num, numLen, count, totalSeq, state, visited, stateLen + 1);
            visited[i] = 0;
        }
    }
}

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}


int** permuteUnique(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int** totalSeq = (int**)malloc(sizeof(int*) * 1000);
    *returnSize = 0;
    _Bool *visited = calloc(numLen, sizeof(_Bool));
    int* state = (int*)malloc(sizeof(int) * numLen);
    int stateLen = 0;

    qsort(num, numLen, sizeof(int), cmp);
    printf("DONE");
    backsearch(num, numLen, returnSize, totalSeq, state, visited, stateLen);
    *returnColumnSizes = (int*)malloc((*returnSize) * sizeof(int));
    for(int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = numLen;
    }

    free(visited);
    free(state);

    return totalSeq;
}