leetcode做题笔记46

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路一：回溯

void swap(int *nums,int index1,int index2)
{int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;
}void prem(int* nums, int numsSize, int* returnSize, int** returnColumnSizes,int** returnNums,int offset)
{if(offset == numsSize){returnNums[*returnSize] = (int *)malloc(sizeof(int ) * numsSize);memcpy(returnNums[*returnSize],nums,sizeof(int) * numsSize );(*returnColumnSizes)[*returnSize] = numsSize;*returnSize = *returnSize + 1;}else{int i;for(i = offset; i < numsSize; i++){swap(nums,i,offset);prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,offset+1);swap(nums,i,offset);}}
}int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{int **returnNums = (int **)malloc(sizeof(int *) * 721);*returnColumnSizes= (int *)malloc(sizeof(int ) * 721);*returnSize = 0;prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,0);return returnNums;}

分析：

本题考虑到要列举所有可能的情况，故考虑使用回溯算法。编写prem函数来进行回溯，当遍历到末尾时申请一个新的空间来存放新的情况，否则就将i和offset交换。不断将新的情况的值赋给新的数组。最后输出数组。

总结：

本题考察了回溯算法的应用，要将回溯的各种情况考虑清楚后方能解决。