LeetCode-46 全排列

原题目

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

示例:

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

题目大意

如题。。

题目分析

这道题目可以用标准的深搜回溯来做。

思路

1.标准深搜回溯 2.交换数值

代码

1.第一种方法。

void backtrace(int *nums,int numsSize,int *returnSize,int **returnColumnSizes,int **arr,int *example,int *flag,int depth) { if(depth == numsSize) { arr[(*returnSize)] = (int *)malloc(sizeof(int*) * depth); for(int i = 0; i < numsSize; i++) { arr[*returnSize][i] = example[i]; } (*returnColumnSizes)[*returnSize] = numsSize; (*returnSize)++; return; } for(int i = 0; i < numsSize; i++) { if(flag[i])continue; flag[i] = 1; example[depth] = nums[i]; backtrace(nums,numsSize,returnSize,returnColumnSizes,arr,example,flag,depth+1); flag[i] = 0; } } int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ if(nums == NULL) { return NULL; } int **arr = (int **)malloc(sizeof(int*)*1000); if(arr == NULL) { return NULL; } memset(arr,0,sizeof(int *) * 1000); *returnColumnSizes = (int *)malloc(sizeof(int) * 1000); if(returnColumnSizes == NULL) { return NULL; } memset(*returnColumnSizes,0,sizeof(int) * 1000); *returnSize = 0; int *example = (int *)malloc(sizeof(int) * numsSize); if(example == NULL) { return NULL; } memset(example,0,sizeof(int) * numsSize); int *flag = (int*)calloc(sizeof(int), numsSize); backtrace(nums,numsSize,returnSize,returnColumnSizes,arr,example,flag,0); free(flag); free(example); return arr; }

2.第二种方法

#define MAX_SIZE 5000 static void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } static void dfs(int* nums, int numsSize, int* returnSize, int** returnColumnSizes, int** ppRes) { static int slow = 0; int fast = 0; if (slow == numsSize) { ppRes[*returnSize] = (int*)malloc(numsSize * sizeof(int)); memcpy(ppRes[*returnSize], nums, numsSize * sizeof(int)); (*returnColumnSizes)[*returnSize] = numsSize; (*returnSize)++; } else { for (fast = slow; fast <= numsSize - 1; fast++) { swap(nums + slow, nums + fast); slow++; dfs(nums, numsSize, returnSize, returnColumnSizes, ppRes); slow--; // 回溯 swap(nums + slow, nums + fast); } } } int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ int** ppRes = (int**)malloc(MAX_SIZE * sizeof(int*)); *returnSize = 0; *returnColumnSizes = (int*)malloc(MAX_SIZE * sizeof(int)); dfs(nums, numsSize, returnSize, returnColumnSizes, ppRes); return ppRes; } 作者：hua-jia-wang-tie-nan（还没有自己写）