The full arrangement of the 46th question in C language.Backtracking

Given an array nums without repeating numbers, return all possible permutations of it.You can return answers in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Tip:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All integers in nums are different from each other

Source: LeetCode
Link: https://leetcode.cn/problems/permutations
The copyright belongs to LeetCode.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Retraction method: As the name suggests, by means of one trial or one result.Execute according to the conditions to achieve the goal.When a step does not match, or fails to reach the goal, go back to the previous one and try the rest.This method of going back to the other way when you can't get through is called the backtracking method.
This topic [full arrangement of arrays] does not contain repetitions.This problem is especially suitable for using the method of backtracking to solve:
Here, let’s first understand the meaning of permutation and combination:
Permutation: A collection of elements arranged in an orderly manner.
Combination: A collection regardless of the sorting order.
Understand the combination arrangement by example:
Arrangement example: such as 1, 2, 3 arrangement method A3_3 = 3! = 3 * 2 * 1 = 6 kinds
Combination example: such as 1, 2, 3The combination method of C3_3 = 1
Then here is the permutation problem:
The full sorting of 1, 2, and 3 needs to be done to calculate.
Might as well think about it without mathematical methods:
Subscript [0]1 -> [1]2 -> [2]3
The first step is to fix a number at the [0] subscript at a time, the problem starts from 3!-> 3 * 2!
Part 2 Each time a number is fixed at the [1] subscript, the problem starts from 3!-> 321
Repeat steps 1 and 2 to wait for all results.
This is also very abstract, may wish to use concrete examples to represent;

3 possible 2 possible 1 possible
[0]1 ---- |
fixed |
fixed |
[1]2 ---- |
fixed |
fixed |[2]3
 Result--(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){// traverse to the end//Apply for returnNumsreturnNums[*returnSize] = (int *)malloc(sizeof(int ) * numsSize);//Copy the content to returnNumsmemcpy(returnNums[*returnSize],nums,sizeof(int) * numsSize );//Record the length of the current copy content(*returnColumnSizes)[*returnSize] = numsSize;*returnSize = *returnSize + 1;}else{//The core of the backtracking algorithmint i;for(i = offset; i < numsSize; i++){swap(nums,i,offset);//i and offset exchangeprem(nums,numsSize,returnSize,returnColumnSizes,returnNums,offset+1);swap(nums,i,offset);//i and offset exchange}}}int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){//Full sort of unique numbers//The number of combinations is n!= n * ( n - 1) * ( n - 2) ...... 2 * 1//This method is suitable for backtracking methods//value range 1 <= nums.length <= 6 = 6 * 5 * 4 * 3 *2 * 1 = possible in 720int **returnNums = (int **)malloc(sizeof(int *) * 721);*returnColumnSizes= (int *)malloc(sizeof(int ) * 721);*returnSize = 0;prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,0);return returnNums;}