Print all combinations of parenthesis

Given number N print all legal parenthesis combination which are possible.

for example for N = 3

( ( ( ) ) )

( ( ) ( ) )

( ( ) ) ( )

( ) ( ( ) )

( ) ( ) ( )

#include

#define N 3

int count = 0;

void printArr(int arr[]) {

int i = 0;

for (i = 0; i < N * 2 ; i++) {

if (!arr[i]) {

printf("( ");

}

else if (arr[i] == 1){

printf(") ");

}

}

printf("\n");

count++;

}

void printParanthesis(int arr[], int index, int lcount, int rcount) {

if (lcount < N) {

arr[index] = 0;

printParanthesis(arr, index + 1, lcount + 1, rcount);

}

if (lcount > rcount) {

arr[index] = 1;

if ((index + 1) == (N * 2)) {

printArr(arr);

}

else {

printParanthesis(arr, index + 1, lcount, rcount + 1);

}

}

}

Unique Paths in m*n grid

Source

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

Combinatorial Solution: It turns out this problem could be solved using combinatorics, which no doubt would be the most efficient solution. In order to see it as a combinatorial problem, there are some necessary observations. Look at the 7×3 sample grid in the picture above. Notice that no matter how you traverse the grids, you always traverse a total of 8 steps. To be more exact, you always have to choose 6 steps to the right (R) and 2 steps to the bottom (B). Therefore, the problem can be transformed to a question of how many ways can you choose 6R‘s and 2B‘s in these 8 steps. The answer is C(8,2) (or C(8,6)). Therefore, the general solution for a m x n grid is C(m+n-2, m-1).