Brackets - number of possible soltions

Given a string containing only the symbols '?', '(' and ')'. You can replace the '?' with either '(' or ')'. Your task is to write a function that tells the number of possible solutions where brackets are used correctly.
Example:
Given the string "?(????)?" the function should return 6.
The correct possible solutions are:
((()()))
(((())))
(())(())
(()(()))
((())())
(()()())

Here is one recursive solution. Three parameters are passed to the function - the given string, the current index of the string and count - an integer calculated based on the brackets - if '(' we add 1 to count and if ')' we decrease count by one. We start iteration over the string's characters starting from the first. If the current symbol is '(' or ')', the the count is recalculated and the iteration goes on. If the current symbol is '?', then there are 2 possibilities either '(' or ')' and that gives 2 branches of the recursion.

long bracket(String str, int index, int count) {
    int n = str.length() - 1;
    long solution = 0;

    if (index > n) {
        if (count == 0)
            solution = 1;
        else
            solution = 0;
    } else {
        if (count < 0)
            solution = 0;
        else

        if (str.charAt(index) == '(')
            solution = bracket(str, index + 1, count + 1);
        else if (str.charAt(index) == ')')
            solution = bracket(str, index + 1, count - 1);
        else if (str.charAt(index) == '?') {
            solution = (bracket(str, index + 1, count + 1) + bracket(str, index + 1, count - 1));
        }
    }

    return solution;
}

The next solution uses the Dynamic Programming method. Here we create a table where we build a row based on the previous row. Here is an explanation of the table. Let's look the string "??(???". We consider two parameters - our two dimensions of the table:
- count: number_of_opening_brackets - number_of_closing_brackets
- index: this is the index of the current character we look at
If the last one is a "?" or ')' - there is one possible solution and if it is '(' there is no solution. That means the last row of our table will be 0, 1, 0, 0... Only in case the last symbol is '(', there will be, obviously, no solutions at all. This is a special case. Imagine, we are now considering the penultimate symbol. Based on the count number and the symbol staying in this position, we calculate the penultimate row. In our case the penultimate symbol is '?'. If count is 0, then we place '(' instead of the '?' and continue. If count is 1, there is no way we can have count 0 in the end no matter what we place instead of the '?'. If count is 2, then we write ')' in place of the '?' and continue. The rest of the count values - 3, 4, 5, won't give a solution. That means our penultimate row will be 1, 0, 1, 0, 0...
We actually build row i based on row (i+1). The logic is the following:
if the symbol is ')' then cell[i][j] = cell[(i + 1)][j - 1];
if the symbol is '(' then cell[i][j] = cell[(i + 1)][j + 1];
if the symbol is '?' then cell[i][j] = cell[(i + 1)][j - 1] + cell[(i + 1)][j + 1];

Our answer is the value in cell[0][0].

long bracketDP(String str) {
    int strLength = str.length() - 1;

    for (int i = 0; i <= strLength; i++) {
        arr[strLength][i] = 0;
    }

    if (str.charAt(strLength) != '(')
        arr[strLength][1] = 1;

    for (int i = strLength - 1; i >= 0; i--) {// index
        for (int j = 0; j <= strLength; j++) {// count
            if (j == 0) {
                if (str.charAt(i) == ')')
                    arr[i][j] = 0;
                if (str.charAt(i) == '(')
                    arr[i][j] = arr[(i + 1)][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i][j] = arr[(i + 1)][j + 1];
                }
            } else {
                if (str.charAt(i) == ')')
                    arr[i][j] = arr[(i + 1)][j - 1];
                if (str.charAt(i) == '(')
                    arr[i][j] = arr[(i + 1)][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i][j] = arr[(i + 1)][j - 1] + arr[(i + 1)][j + 1];
                }
            }
        }
    }
    return arr[0][0];
}

In fact, constructing each row all we need is the previous row. It means that we can do with memory reserved for only two rows - we use one to construct the second and then we use the second and write the results to the first one. Then we again use row one to construct the second row, and so on. Here is an optimization we can do:

long bracketDP2(String str) {
    int strLength = str.length() - 1;

    for (int i = 0; i <= strLength; i++) {
        arr[strLength % 2][i] = 0;
    }

    if (str.charAt(strLength) != '(')
        arr[strLength % 2][1] = 1;

    for (int i = strLength - 1; i >= 0; i--) {// index
        for (int j = 0; j <= strLength; j++) {// count
            if (j == 0) {
                if (str.charAt(i) == ')')
                    arr[i % 2][j] = 0;
                if (str.charAt(i) == '(')
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                }
            } else {
                if (str.charAt(i) == ')')
                    arr[i % 2][j] = arr[(i + 1) % 2][j - 1];
                if (str.charAt(i) == '(')
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i % 2][j] = arr[(i + 1) % 2][j - 1] + arr[(i + 1) % 2][j + 1];
                }
            }
        }
    }
    return arr[0][0];
}

For more brackets problems visit "Bracket combinations"