(LeetCode)全排列

目录

题目要求

题目理解以及思路分析

代码分部讲解

第一部分

第二部分

---

题目要求

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

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]
 

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

来源：力扣（LeetCode）
 

        上一篇讲的组合总数，运用的是回溯法。对于这道题相信很多人也会想到使用回溯法去解决，当然了回溯法之前说过了几乎是万能的解法，但是不合理的使用回溯法往往会使得程序变得冗长，运行超时等等。

题目理解以及思路分析

        1.首先先来理解题目，很简单对吧，其实就是数学上面的排列组合问题，数学上对于这种问题都有一个固定的公式去求解，但是很显然计算机上并没有这样的捷径。但~~~，不要担心，计算机有计算机的解法，熟悉了方法后你会发现 “人算不如天算”（嘿嘿）。

        2.明白了题目后就来说说思路，其实完全可以从不接触算法公式的小白去求解简单的数列的数学方法类似的思路。想想看，我们如果没有学数学上的公式的话，那对于这样的比较简单的题目该怎么去求解呢？怎么样？是不是明白了——对喽，就是用最最最最朴素的方法一个一个一个的列出来嘛。

        3.就算是一个一个的列出来，那我们也得有一个便捷的方法去排列啊，这样才能保证我们不漏不重。大多数人习惯的方法就是以第一个数字作为开头列举可能的结果，然后再以第二个数字为开头不动...........就这样以此类推。这样的方法是不是非常适合用我们计算机中的回溯法去求呢？

        既然理解了题目又搞懂了思路，那接下来我们就用 “事实说话”！！！

        GO！GO！GO！

代码分部讲解

第一部分

int count;   //定义全局变量
 
//回溯法
void backTrack(int* nums, int numsSize, int depth, int* path, bool* used, int** result)
{
  int i;   //定义变量
  if(depth == numsSize)   //判定条件
    {
      result[count] = (int*)malloc(sizeof(int)* numsSize);   //为返回数组分配空间
      memcpy(result[count++], path, sizeof(int)* numsSize);   //将此路径的值赋值给返回数组
      return;
    }
  for(i = 0; i < numsSize; i++)
    {
      if(used[i] == true)   //起到一个判定的作用
        continue;
      path[depth] = nums[i];   //将符合的值赋给该路径数组中
      used[i] = true;   //将该数据进行标记
      backTrack(nums, numsSize, depth + 1, path, used, result);   //回溯
      used[i] = false;   //清除
    }
}

        这一部分是整个程序的核心，也是上述思路的一个实体化表现。

        对一些地方着重讲解一下：

  for(i = 0; i < numsSize; i++)
    {
      if(used[i] == true)   //起到一个判定的作用
        continue;
      path[depth] = nums[i];   //将符合的值赋给该路径数组中
      used[i] = true;   //将该数据进行标记
      backTrack(nums, numsSize, depth + 1, path, used, result);   //回溯
      used[i] = false;   //清除
    }

很多读者可能不理解的一步是：

      if(used[i] == true)   //起到一个判定的作用
        continue;

        其实很好理解，但是首先必须清楚 bool函数 ，这个函数在这里不过多的讲解，仅仅粗略的讲解一下它的用法，这个函数其实是一种判定，它最后的结果仅仅只有 true 和 false 两种，其中 0 为 false，0！为 true。

        明白这些后再来看这段代码——仅仅用作判断，那问题来了？它判断的到底是什么呢？  其实它判断的是这个数据之前有没有被使用过（也就是说再排列过程中有没有可能是它已经被使用过了？）这样就保证排列过程中数据被重复使用的情况。

当然，对于这一段：

used[i] = false;   //清除

        更简单了，认真看过上一篇文章的读者应该很快明白了。这一步就是回溯法模板中所提到的，用于对之前有影响的数据进行一个清除。仍不明白的读者可以去参考上一篇文章或者评论区留言都可。

第二部分

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 1;   //初始化
    int i;
    for(i = 1; i <= numsSize; i++)   //计算返回数组行数为全排列的总数
      {
        (*returnSize) *= i;
      }
    *returnColumnSizes = (int*)malloc(sizeof(int)* (*returnSize));   
    for(i = 0; i < (*returnSize); i++)   //计算返回数组中每行的列数
      {
        (*returnColumnSizes)[i] = numsSize;
      }
    bool* used = (bool*)calloc(numsSize, sizeof(bool));  //分配空间
    int** result = (int**)malloc(sizeof(int*)* (*returnSize));   //分配空间
    int* path = (int*)malloc(sizeof(int)* (numsSize));   //分配空间
    count = 0;   //初始化
    backTrack(nums, numsSize, 0, path, used, result);   //调用函数
 
    return result;   //返回函数
 
}

         这一步就相对来说很简单了，主要就是对上一步的函数进行一些定义和配置。

    for(i = 1; i <= numsSize; i++)   //计算返回数组行数为全排列的总数
      {
        (*returnSize) *= i;
      }

        这个其实用的就是数学中的计算方法，我们仅仅只需要知道个数的总数即可，不必考虑它的每一种情况。