Question

I did write a code to print all valid combinations of n-pair parentheses. However, at my first try, the algorithm output all the combinations twice, that is, . The code was:

public static void solve(char[] string, int open, int closed, int index)
{
    if (open < 0 || closed < open) {
        return;
    }

    if (open == 0 && closed == 0) {
        System.out.println(string);
    }

    if (open > 0) {
        string[index] = '(';
        solve(string, --open, closed, ++index);
    }

    if (closed > open) {
        string[index] = ')';
        solve(string, open, --closed, ++index);
    }
}

I spend a significant amount of time in order to see what went wrong. I figured the code went into the last if branch more than it should. Then, while trying different things, I realized changing

solve(string, --open, closed, ++index);

to

solve(string, open-1, closed, ++index);

changed the outcome. This resulted in getting a java.lang.ArrayIndexOutOfBoundsException. Finally, I replaced all pre-increment operations with corresponding arithmetic operations(e.g., ++index to index+1) and the code ran correctly.

My question is, shouldn't --open and open-1 calculate and send the same value as parameter to the function? How come the code behaves differently when they should calculate the same value?

Was it helpful?

Solution

solve(string, --open, closed, ++index);

actually changes open to be one less than before, which makes the next use of open just below act on a value 1 less than passed in.

solve(string, open-1, closed, ++index);

...on the other hand passes open-1 into the solve method, but does not change open, so it's used unchanged when used in later statements.

OTHER TIPS

Actually --x is a pre decrement operation which will always be same as x=x-1;

ie decrement x by 1 first and then assign decremented value of x to x.

so x value will definitely changes when we perform --x.

but x-1 is just an operation we are doing on x and operation is subtract.

here we are assigning this result into some argument in the method which is receiving this call. but its not reassigned to x automatically.

so x-1 is never ever equals x=x-1; and hence x remains same, only receiver gets subtracted value.

hence

solve(string, --open, closed, ++index);

in the above statement , pre decrement is performed on open.

so it is same as open=open-1; and hence open value changed.

but

solve(string, open-1, closed, ++index);

above statement is subtracting 1 from open and passing subtratced value to method.

its same as receiveing_variable_in_method_definition = open-1 but open is not changing.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top