C语言力扣第46题之全排列。回溯法

给定一个不含重复数字的数组 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）
链接：https://leetcode.cn/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回缩法：顾名思义，通过一次一次尝试或者结果的办法。按照条件往下执行，以达到目标。当某一步不符，或者达不到目标时，回到前一次，尝试其余的可能。这种路走不通就退回走其他的的方法就称为回溯法。
本题目【数组的全排列】不包含重复。这道题尤其适合使用回溯的方法来求解：
这里先要科普下，排列和组合的含义：
排列：有序排列的元素的集合。
组合：不管排列顺序的集合。
通过举例来了解组合排列：
排列举例：如1，2 ，3的排列方法A3_3 = 3! = 3 * 2 * 1 = 6种
组合举例：如1，2，3的组合方法 C3_3 = 1种
那么这里是排列问题：
1，2 ，3的全排序需要做才能计算出来。
不妨不用数学的方法来思考：
下标[0]1 -> [1]2 -> [2]3
第一步 每次固定一个数字在 [0]下标处，问题就从3！-> 3 * 2!
第二部 每次固定一个数字在 [1]下标处，问题就从3！-> 321
重复步骤1和步骤2，就能等到所有的结果。
这样所也很抽象，不妨用具体的示例来表示;

可能3种    可能2种  可能1种
[0]1  ----  |
固定        |
          [1]2 ---- |
          固定      |
            |      [2]3
            |    得到结果 --(1,2,3)
            |
           [1]3 ----|
                    |
                    [2]2
                  得到结果 --(1,3,2)

void swap(int * nums,int indexA,int indexB)
{
    int temp    = nums[indexA];
    nums[indexA]= nums[indexB];
    nums[indexB]= temp;
}

void prem(int* nums, int numsSize, int* returnSize, int** returnColumnSizes,int** returnNums,int offset)
{
    if(offset == numsSize)
    {
        //遍历到末尾了
        //申请returnNums
        returnNums[*returnSize] = (int *)malloc(sizeof(int ) * numsSize);
        //拷贝内容到returnNums
        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);//i 和 offset 交换
            prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,offset+1);
            swap(nums,i,offset);//i 和 offset 交换
        }
    }
}


int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    //不重复的数字的全排序
    //组合次数为 n！= n *( n - 1) *( n - 2) ...... 2 * 1
    //这样的方法适合回溯的方法
    //取值范围1 <= nums.length <= 6  = 6 * 5 * 4 * 3 *2 * 1 = 720中可能
    int **returnNums = (int **)malloc(sizeof(int *) * 721);
    *returnColumnSizes= (int *)malloc(sizeof(int ) * 721);
    *returnSize = 0;
    prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,0);
    return returnNums;

}