Medium
Given an array nums of distinct integers, return all the possible permutations. You can return the answer 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]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void addResult(int** result, int* returnSize, int* columnSizes, int* currResult, int numsSize) {
result[*returnSize] = malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; i++) {
result[*returnSize][i] = currResult[i];
}
columnSizes[*returnSize] = numsSize;
(*returnSize)++;
}
void permuteRecur(int* nums, int numsSize, int** result, int* returnSize, int* columnSizes, int* currResult, bool* used, int currIndex) {
if (currIndex == numsSize) {
addResult(result, returnSize, columnSizes, currResult, numsSize);
return;
}
for (int i = 0; i < numsSize; i++) {
if (used[i]) {
continue;
}
currResult[currIndex] = nums[i];
used[i] = true;
permuteRecur(nums, numsSize, result, returnSize, columnSizes, currResult, used, currIndex + 1);
used[i] = false;
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int** result = malloc(1000 * sizeof(int*)); // Allocate space for result
*returnSize = 0;
*returnColumnSizes = malloc(1000 * sizeof(int)); // Allocate space for column sizes
bool* used = calloc(numsSize, sizeof(bool));
int* currResult = malloc(numsSize * sizeof(int));
permuteRecur(nums, numsSize, result, returnSize, *returnColumnSizes, currResult, used, 0);
free(used);
free(currResult);
return result;
}