#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FACT(n) ((n) <= 1 ? 1 : \
(n) == 2 ? 2 : \
(n) == 3 ? 6 : \
(n) == 4 ? 24 : \
(n) == 5 ? 120 : \
(n) == 6 ? 720 : \
(n) == 7 ? 5040 : \
(n) == 8 ? 40320 : \
(n) == 9 ? 362880 : \
(n) == 10 ? 3628800 : \
(n) == 11 ? 39916800 : \
(n) == 12 ? 479001600 : INT_MAX)
#define CATALAN(n) (FACT(2 * n)) / (FACT(n + 1) * FACT(n))
static char** output;
static int current_i = 0;
static int OUTPUT_LENGTH;
static int MAX_LENGTH;
char** generateParenthesis(int n, int* returnSize) {
OUTPUT_LENGTH = CATALAN(n); // this is how much the array's length will be calculated using formula
MAX_LENGTH = 2*n; //this is the max length of string (n times opening bracket & n times closing bracket) without null terminator counted in.
//allocate just the right amount of memory for the array
output = calloc(OUTPUT_LENGTH, sizeof(char*));
backtrack(0, 0, calloc(MAX_LENGTH + 1, sizeof(char)));
*returnSize = OUTPUT_LENGTH;
return output;
}
void backtrack(int opening, int closing, char* str) {
//when the string reaches the maximal length
if (strlen(str) == MAX_LENGTH) {
//set the current element of the array to point to the string
output[current_i] = str;
current_i++;
//and return
return;
}
if (opening < MAX_LENGTH / 2) {
char* new = calloc(MAX_LENGTH+1, sizeof(char));
strcpy(new, str);
new[strlen(str)] = '(';
backtrack(opening + 1, closing, new);
}
if (closing < opening) {
char* new = calloc(MAX_LENGTH+1, sizeof(char));
strcpy(new, str);
new[strlen(str)] = ')';
backtrack(opening, closing + 1, new);
}
//free the unneeded strings to not leak
free(str);
}```#Heap overflow? Solving Leetcode #22. Generating Parentheses
short abyss
velvet berryBOT
short abyss
The error is on line #39 or output[current_i] = str;.
When I set the char* to point to the it report heap overflow and I couldn't find why it occurs
random remnant
How much heap space do you believe your machine has? The fact is that calloc/malloc calls can and do fail when insufficient memory is available. What value are you passing to calloc when this happens? Secondarily, it looks like you are not carefully tending to terminating null characters required by strlen and strcpy.
short abyss
Well on leet code it fails no matter what (probably due to them compiling with address sanitizer) while me running on Windows I got no address sanitizer. When I compile it on my machine with latest gcc version and no optimizations all works great until I input that n = 8. Then the program just crashes.
short abyss
How much heap space do you believe your machine has? The fact is that calloc/ma...
What do you mean I'm not tending to terminate null characters required by strlen and strcpy? If it means that I'm not placing them, with calloc all the memory is zeroed so all strings should be null terminated no matter what
unless I overwrite the null terminator somehow but I'm pretty sure I am not
cosmic rover
What I can see by testing the code quickly is that with n = 8, OUTPUT_LENGTH is 1
So with this line
output = calloc(OUTPUT_LENGTH, sizeof(char*));
output can only have 1 char*
But then there
output[current_i] = str;
current_i is out of bounds
random remnant
good point about the use of calloc. my comment was just that you were not specifically replacing them in the code. if you pass n = 8 to CALCAN then CALCAN is going to pass 2 * n to FACT which is going to return INT_MAX which will then be divided by (INT_MAX * INT_MAX) which is an integer overflow, so the result will be undefined. On my machine it returns 2147483647 which of course will create your heap overflow.
short abyss
good point about the use of calloc. my comment was just that you were not speci...
Never would've thought this would be the problem. Thank you!
!solved
velvet berryBOT