跳转至

46. 全排列

难度：中等

题目

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Reference

题解

使用回溯算法，对于给定的序列：

  • 若长度为1，则只有一种排列方式，直接返回
  • 若长度大于1，则可以：
    • 将序列中第一个数放在排列的第一位，然后与后面部分的全排列合并
    • 将序列中第二个数放在排列的第一位，然后与后面部分的全排列合并
    • ……
    • 将序列中最后一个数放在排列的第一位，然后与后面部分的全排列合并
    • 最终结果包含如上所有的排列。

对于长度为\(n\)的序列，共有\(n!\)种排列。

int fact(int x)
{
    if (!x)
        return 0;
    int i = 1, ret = 1;
    for (i = 1; i <= x; i++)
        ret *= i;
    return ret;
}
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    if (numsSize < 2)
    {
        *returnSize = 1;
        *returnColumnSizes = (int *)malloc(sizeof(int) * *returnSize);
        *returnColumnSizes[0] = numsSize;
        if (numsSize == 0)
            return NULL;
        int **ret = (int **)malloc(sizeof(int *) * *returnSize);
        *ret = (int *)malloc(sizeof(int));
        **ret = *nums;
        return ret;
    }
    *returnSize = fact(numsSize);
    *returnColumnSizes = (int *)malloc(sizeof(int *) * *returnSize);
    int *sub = (int *)malloc(sizeof(int) * numsSize), i = 0, **rec = NULL, recSize, *recColSize,
        **ret = (int **)malloc(sizeof(int *) * *returnSize), retpos = 0, j = 0;
    for (i = 0; i < *returnSize; i++)
        (*returnColumnSizes)[i] = numsSize;
    for (i = 0; i < numsSize; i++)
    {
        sub = memcpy(sub, nums, sizeof(int) * numsSize);
        swap(sub + i, sub);
        rec = permute(sub + 1, numsSize - 1, &recSize, &recColSize);
        for (j = 0; j < recSize; j++)
        {
            ret[retpos] = (int *)malloc(sizeof(int) * numsSize);
            ret[retpos][0] = sub[0];
            memcpy(ret[retpos] + 1, rec[j], sizeof(int) * (numsSize - 1));
            retpos++;
        }
    }
    return ret;
}

评论