Algoritmi di confronto e complessità

Voglio risolvere questo problema:

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.

La mia prima soluzione è:

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);
}

E penso che la complessità sia O (N ^ 2) , I I Wrong?

Il secondo algoritmo è:

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);
}

Qual è la complessità del secondo algoritmo?
Quale preferisci e perché?