- C语言
- 注意点
- 结果
- 题目
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void bt(char ***ret, int *retsize, int *retcap, char *buf, int l, int r, int n) {
if (l > n || r > n) {
return;
}
if (r > l)
return;
if (l == r && r == n) {
*retsize += 1;
if (*retsize > (*retcap - 2)) {
*retcap = (*retcap) << 1;
*ret = realloc(*ret, (*retcap) * sizeof(char *));
}
(*ret)[(*retsize)-1] = strdup(buf);
return;
}
buf[l+r] = '(';
bt(ret, retsize, retcap, buf, l+1, r, n);
buf[l+r] = ')';
bt(ret, retsize, retcap, buf, l, r+1, n);
}
char ** generateParenthesis(int n, int* returnSize){
int size = 0;
int cap = 0;
char **ret = NULL;
char buf[64] = {0};
cap = 1 << 4;
ret = calloc(cap, sizeof(char *));
bt(&ret, &size, &cap, &buf[0], 0, 0, n);
*returnSize = size;
return ret;
}
注意点
- 递归控制条件
l <= n || r <= n
必须满足,避免无线扩张; - 未知最后的总条数,根据实际去动态生成
char *
数目,总数不是(1<<(n-1))
; - 优化
ret
的生成的时候,注意ret
的预分配,如ret = calloc(...)
否则影响ret = realloc(...)
的逻辑;
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)