Combinations of n-pairs of parentheses

Question

I have a very basic question about an algorithm to print all valid combinations of n-pairs of parentheses. I printed out the value of l, r and string s. But for the following code, after printing out the first combination which is (()), how the value of l and r become 1 and 0 so that it can start the second combination ()()?

static void brackets (int l, int r, String s) {
    System.out.println(l + "" + r + " s:" + s);
    if (l == 0 && r == 0) {
        System.out.println(s);
    }
    if (l > 0) {
        brackets(l-1, r+1, s + "(");
    }
    if (r > 0) {
        brackets(l, r-1, s + ")");
    }
}
public static void main(String[] args) {
    brackets(2, 0, "");
}

l and r are left, right parentheses and I was expecting the output of: (()), ()() which are the two combinations of two pairs of parentheses. but how does this code get the second combination ()()? thanks

This question isn't very clear. What is `l`, what is `r`, what's an "n-pair" and why do you expect this algorithm to work? — Dawood ibn Kareem, Jan 09 '14 at 22:57
Check these links. http://stackoverflow.com/questions/727707/finding-all-combinations-of-well-formed-brackets http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/ Hope you can translate this to Java. — peter.petrov, Jan 09 '14 at 23:01
To pose a question well, you should include likely inputs and expected outputs. — Nathaniel Ford, Jan 09 '14 at 23:02
I would try to somehow map the paring to the bits of a binary number, and interpret the (repeatedly incremented) number to "build" each set. — Hot Licks, Jan 09 '14 at 23:03
l and r are left/right parentheses and I was expecting the output of: (()), ()() which are the two combinations of two pairs of parentheses — Zzz..., Jan 09 '14 at 23:14
If `l` and `r` are the number of left/right parentheses, shouldn't they start out the same? And in your recursive calls, shouldn't `l-r` decrease by 1 if you add `(` to the string, and increase by 1 if you add `)`? I'm not saying that fixing these problems will make it work, but it seems like these are invariants that should hold that you're violating. — ajb, Jan 09 '14 at 23:33
The situation can be modeled as a binary number, where `1` represents `(` and `0` represents `)`. The number must begin with a `1` and end with a `0` and contain an equal number of ones and zeros. It should be fairly easy to increment an integer and pick out the combos that meet these criteria. — Hot Licks, Jan 10 '14 at 11:44
I realized walking into the gym this AM that I got the qualification test slightly wrong. One should start at the left-most 1 bit (a '(') and increment a counter for each 1, decrement for each zero. If the count goes negative the number is disqualified. It is then possible to use a sort of "look-ahead" to go on the the next valid sequence: Set the offending 0 bit to 1 and replace all bits to the right with a 1010.. sequence. Then continue where you left off. — Hot Licks, Jan 10 '14 at 16:27

peter.petrov · Answer 1 · 2014-01-09T23:09:20.130

Running your code I am not sure if that's exactly what you're looking for.

But if it is - here is the Java port of the code in the links I provided above.

public class Test0010  {

    public static void main(String[] a) {
        brackets(5);
    }

    public static void brackets(int n) {
        for (int i = 1; i <= n; i++) {
            brackets("", 0, 0, i);
        }
    }

    private static void brackets(String output, int open, int close, int pairs) {
        if ((open == pairs) && (close == pairs)) {
            System.out.println(output);
        } else {
            if (open < pairs)
                brackets(output + "(", open + 1, close, pairs);
            if (close < open)
                brackets(output + ")", open, close + 1, pairs);
        }
    }

}

Pham Trung · Answer 2 · 2014-01-10T02:54:35.970

I believe this is what you want:

To print n pairs of bracket, we observe that there are total n open and n close brackets.

So the code you posted starting with 2 open and 0 close bracket.

So imagine drawing a tree, in each state, we can go into two difference directions:

Either print another open bracket -> decrease l -> so the number of needed close bracket will be increased to make the expression valid -> increase r.
Print a close bracket if r > 0 -> decrease r.

So we can visualize the state as follow:

Starting with (l = 2,r = 0) it go to (1,1) and in this state, it divided into two states: (0,2) and (1,0). So, the code will further break down until both l = 0 and r = 0 to print the result. Hope you understand!

score 0 · Answer 3 · answered Jan 10 '14 at 14:25

Certainly your way of forming all well formed parenthesis is very complex ,here is a more intuitive recursive definition of it : -

S(N) = '('+S(N-1)+')' 

     or 

S(N) = "()"+S(N-1)

Here is a pseudo code using above recursive definition : -

void parenthesis(int l,int r,char[] result) {

   if(l<r) {

        result[l] = '(';
        result[r] = ')';
        parenthesis(l+1,r-1,result);
        result[l] = '(';
        redult[l+1] = ')';
        parenthesis(l+2,r,result);
   }

   else {

           print(result);

   }

}

parenthesis(0,2*N-1,new char[2*N]);

Combinations of n-pairs of parentheses

3 Answers3