Algorithms comparison and complexity

Question

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?

Answer 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.