This question is based around leetcode problem 46: Permutations.
copy of the question for convenience: Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Constraints:
1 <= nums.length <= 6 -10 <= nums[i] <= 10 All the integers of nums are unique.
I am a beginner in C and i'm trying to work on my pointer and malloc skills. I don't have much experience on any of this, so this question is difficult for me.
Leetcode gives a set input you cannot change, and the last input is giving me some trouble. This is the function. int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
I have found a 'solution' to this problem that I checked on examples in VS code. This is the solution.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.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().
*/
/*
numsSize is max 6.
*/
void backTrack(int** res, int* nums, int numsSize, int* permutation, int permutationSize, bool* used, int* numberadded);
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
// Determine resturnSize
int factorialLookUpTable[6] = {1,2,6,24,120,720};
*returnSize = factorialLookUpTable[numsSize-1];
// Malloc
int **returnedArray = malloc(sizeof(int*)* (*returnSize)); // An array that hold 'returnSize' pointers.
// Inititalizing the arrays inside returnedArray
for(int i = 0; i< *returnSize; i++){
returnedArray[i] = malloc(sizeof(int)* numsSize);
}
int* permutation = malloc(numsSize*sizeof(int));
bool* used = calloc(numsSize, sizeof(bool));
int numberAdded = 0;
backTrack(returnedArray, nums, numsSize, permutation, 0, used, &numberAdded);
return returnedArray;
}
void backTrack(int** res, int* nums, int numsSize, int* permutation, int permutationSize, bool* used, int* numberadded){
if (permutationSize == numsSize){
// Add the permutation to the result.
memcpy(res[*numberadded],permutation,numsSize*sizeof(int));
*numberadded += 1;
return;
}
// Go through all digits and combinations.
for (int i = 0; i < numsSize; i++){
if (! used[i]){
used[i] = true;
permutation[permutationSize] = nums[i];
permutationSize++;
backTrack(res, nums, numsSize, permutation, permutationSize, used, numberadded); // recursion
used[i] = false;
permutation[permutationSize-1] = 0;
permutationSize--;
}
}
}
The biggest issue for me is setting up 'res' and storing data in it so it can be extracted in a simple way. Now this solution 'works' (at least my examples do) but leetcode gives the error: "Line 241: Char 15: runtime error: load of null pointer of type 'int' [Serializer.c]".
My guess is that i had to use returnColumnSizes somewhere, but i have no idea what it means (because it's a pointer to a pointer). Could anyone give me some suggestion on how to improve on this code and how it's ment to be solved? Thanks
What is int** returnColumnSizes?
The calling function (which you do not have access to) will do something like
void checkAnswer(void) {
int values[] = {5, 3, -1, 0, -2, 8};
int rows, *cols;
int **y = permute(values, 6, &rows, &cols);
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols[row]; col++) {
// check y[row][col]
}
}
// free stuff
}