Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 22. Generate Parentheses

---

參考資訊：
https://algo.monster/liteproblems/22
https://www.cnblogs.com/grandyang/p/4444160.html

題目：


解答：

int dfs(int l, int r, int n, char* tmp, char** rbuf, int* rcnt)
{
    int cnt = 0;

    if ((l > n) || (r > n) || (l < r)) {
        return 0;
    }

    if ((l == n) && (r == n)) {
        int pos = (*rcnt)++;
        int len = strlen(tmp);

        rbuf[pos] = calloc(len + 1, sizeof(char));
        strcpy(rbuf[pos], tmp);
        return 1;
    }

    strcat(tmp, "(");
    dfs(l + 1, r, n, tmp, rbuf, rcnt);
    cnt = strlen(tmp);
    if (cnt > 0) {
        tmp[cnt - 1] = 0;
    }

    strcat(tmp, ")");
    dfs(l, r + 1, n, tmp, rbuf, rcnt);
    cnt = strlen(tmp);
    if (cnt > 0) {
        tmp[cnt - 1] = 0;
    }

    return 0;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** generateParenthesis(int n, int* returnSize)
{
    #define MAX_SIZE 20000

    char tmp[MAX_SIZE] = { 0 };
    char** rbuf = calloc(MAX_SIZE, sizeof(char));

    *returnSize = 0;
    dfs(0, 0, n, tmp, rbuf, returnSize);
    return rbuf;
}