3

I want to sole this problem:

Write a method to return all valid combinations of n-pairs of parentheses.

The method should return an ArrayList of strings, in which each string represents a valid combination of parentheses.

The order of the strings in the ArrayList does not matter.

Examples: combParenthesis(2) ==> {"(())","()()"}

Note: Valid combination means that parentheses pairs are not left open. ")()(" is not a valid combination.

My first solution is:

public static ArrayList<String> combParenthesis2(int pairs) {
    ArrayList<String> res = new ArrayList<String>();
    recursive(pairs, pairs, "", res);
    return res;
}

public static void recursive(int left, int right, String build, ArrayList<String> res) {
    if(right == 0 && left == 0) {
        res.add(build);
        return;
    }

    if(left > 0)
        recursive(left-1, right, build + "(", res);

    if(right > left)
        recursive(left, right-1, build + ")", res);
}

And I think the complexity is O(N^2), am I Wrong?

The second algorithm is:

public static ArrayList<String> combParenthesis(int pairs) {
    Set<String> result = new HashSet<>();
    if (pairs <= 0) {
        return new ArrayList<>(result);
    }

    result.add("()");
    if (pairs == 1) {
        return new ArrayList<>(result);
    }

    for (int i=1; i<pairs; i++) {
        Set<String> newSet = new HashSet<>();
        for (String s : result) {
            newSet.add(s + "()");
            newSet.add("()" + s);
            newSet.add("(" + s + ")");
        }
        result = newSet;
    }

    return new ArrayList<>(result);
}

Which is the complexity of the second algorithm?
Which one do you prefer and why?

1

I think you are wrong

How did you come to complexity n^2? The complexity of first approach is O(n!) and the algorithm is correct.

Actually the number of valid combinations is C(n), see https://en.wikipedia.org/wiki/Catalan_number, so asymptotically the complexity is O(4^n).

Your second approach has better complexity (O(3^n)) but is incorrect - produces wrong result. For example it wouldn't list "(())(())" in results which is wrong.

So I prefer the first algorithm, because it is correct.

  • Would you explain how you calculated O(n!) for the first algorithm? Good reference to Catalan Numbers. – Kristian H Nov 24 '16 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.