w3resource

C Exercises: Combinations of parentheses from n pairs


11. Generate Well-Formed Parentheses Variants

Write a C programming to generate all combinations of well-formed parentheses from n given pairs of parentheses.

Example: 
Input  n = 5
Output: 
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()

C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static char** generate_Parenthesis(int n, int* returnSize)
{
    int left_num, right_num, cap = 5000, ctr = 0;
    char *stack = malloc(2 * n + 1);
    char **parentheses = malloc(cap * sizeof(char *));

    char *p = stack;
    left_num = right_num = 0;
    stack[2 * n] = '\0';

    while (p != stack || ctr == 0) {
        if (left_num == n && right_num == n) {
            parentheses[ctr] = malloc(2 * n + 1);
            strcpy(parentheses[ctr], stack);
            ctr++;

            while (--p != stack) {
                if (*p == '(') {
                    if (--left_num > right_num) {
                        *p++ = ')';
                        right_num++;
                        break;
                    }
                } else {
                    right_num--;
                }
            }
        } else {
            /* forward */
            while (left_num < n) {
                *p++ = '(';
                left_num++;
            }
            while (right_num < n) {
                *p++ = ')';
                right_num++;
            }
        }
    }

    *returnSize = ctr;
    return parentheses;
}

int main(void)
{
    int i, ctr;
    i = 5;
    char ** lists = generate_Parenthesis(i, &ctr);
    for (i = 0; i < ctr; i++) {
        printf("%s\n", lists[i]);
    }
    return 0;
}

Sample Output:

((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()

Flowchart:

C Programming Flowchart: Generate all combinations of well-formed parentheses from n given pairs of parentheses.

For more Practice: Solve these Related Problems:

  • Write a C program to generate all combinations of well-formed parentheses for a given number of pairs using backtracking.
  • Write a C program to count the total number of well-formed parentheses combinations for n pairs.
  • Write a C program to generate well-formed parentheses and sort them lexicographically.
  • Write a C program to generate well-formed parentheses combinations while limiting maximum nesting depth.

C Programming Code Editor:



Contribute your code and comments through Disqus.

Previous C Programming Exercise: Check if a given string is valid or not.
Next C Programming Exercise: Remove duplicates from an array of integers.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.